CareerCup

I think the problem statement is not complete due to the missing information what w_extra should do. Since I noticed its a dublicate I already solved (id=5721708662095872) I explain the question as I interpreted it first:

you get the graph as described. you get the w_extra which is the weight of an edge you can place between any two vertices that have not already a direct connection (an edge connecting them). You can only place that extra edge once.

I checked the two sample and it was right:
1) Path is 1->2->4 with weight 4 and no extra edge used
2) Path is 1->5->4 with extra edge used from 1 to 5 (path weight is 2+1 = 3)

I skiped the coding of parsing ala topcoder contest and handcoded the two samples.
The code is long because it has some convenience stuff around it.

#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <vector>
#include <iostream>

struct Edge
{
	int destId_, weight_;

	Edge(int destId, int weight) : destId_(destId), weight_(weight) { }	
};

struct TraversalItem
{
	int vertexId_, cost_, parentId_;
	TraversalItem(int vertexId, int cost, int parentId) 
		: vertexId_(vertexId), cost_(cost), parentId_(parentId) { }
	TraversalItem() : TraversalItem(-1, -1, -1) { }
};

using Path = std::pair<int, std::vector<std::pair<int, bool>>>;

class Graph
{
private:
	const int bonusVertexIdOffset = 100000;
	std::unordered_map<int, std::unordered_map<int, int>> edges_;
	std::unordered_set<int> vertices_;

public:
	void addEdge(int u, int v, int weight)
	{
		if (u >= bonusVertexIdOffset || v >= bonusVertexIdOffset) throw "id out of range";
		edges_[u][v] = weight;
		edges_[v][u] = weight;
		addVertex(u);
		addVertex(v);
	}

	void addVertex(int vertexId) 
	{ 
		if (vertexId >= bonusVertexIdOffset || vertexId >= bonusVertexIdOffset) throw "id out of range";
		vertices_.insert(vertexId);
	}

	// main part of algorithm 
	// it returns the path cost and the visited vertice id's with a flag wether they were in g or g'
	Path getShortestPathWithBonusEdge(int start, int end, int bonusWeight)
	{
		auto tiComparer = [](const TraversalItem& a, const TraversalItem& b) -> bool { return a.cost_ > b.cost_; };
		std::priority_queue<TraversalItem, std::vector<TraversalItem>, decltype(tiComparer) > tqueue(tiComparer);
		std::unordered_map<int, TraversalItem> state;

		tqueue.push(TraversalItem(start, 0, -1)); // start with start
		state.emplace(std::pair<int, TraversalItem>(start, TraversalItem(start, 0, -1))); // start must be in state, too
		while (tqueue.size() > 0)
		{
			auto u = tqueue.top();
			tqueue.pop();

			int uId = u.vertexId_;
			if (uId == end || uId == end + bonusVertexIdOffset)
			{
				end = uId; // path end id, it might be in g'
				break; // if end is now the cheapest to reach: done
			}
			auto edges = getOutEdges(uId, bonusWeight);
			for (auto edge : edges)
			{
				int cost = u.cost_ + edge.weight_;
				int vId = edge.destId_;
				auto vStateIt = state.find(vId);
				if (vStateIt == state.end())
				{
					TraversalItem ti(vId, cost, uId);
					vStateIt = state.emplace(std::pair<int, TraversalItem>(vId, ti)).first;
					tqueue.push(ti); 
				}
				else if(vStateIt->second.cost_ > cost)
				{
					vStateIt->second.cost_ = cost;
					vStateIt->second.parentId_ = uId;
					tqueue.push(vStateIt->second); // since there's no update-key function... 
				}			
			}
		}

		// reconstruct path
		auto stateIt = state.find(end);
		if (stateIt != state.end())
		{
			// reached the end
			std::vector<std::pair<int, bool>> path;
			int vertexId = stateIt->second.vertexId_;
			int cost = stateIt->second.cost_;
			while (vertexId != -1)
			{
				bool gs = vertexId >= bonusVertexIdOffset;
				int vId = gs ? vertexId - bonusVertexIdOffset : vertexId;
				path.push_back(std::pair<int, bool>(vId, gs));
				vertexId = state[vertexId].parentId_;
			}
			return Path(cost, std::vector<std::pair<int, bool>>(path.rbegin(), path.rend()));
		}
		return Path(-1, std::vector<std::pair<int, bool>>()); // empty path
	}

private:
	std::vector<Edge> getOutEdges(int vertexId, int bonusEdgeWeight)
	{
		std::vector<Edge> edges;
		
		int u = vertexId;
		int vIdOffset = 0;
		if (u >= bonusVertexIdOffset)
		{
			u -= bonusVertexIdOffset;
			
			// bonusedge already used, so only original edges are possible
			auto edgeIt = edges_.find(u);
			if (edgeIt != edges_.end())
			{
				for (auto v : edgeIt->second)
				{
					// use orginial edge but stay in g'
					edges.push_back(Edge(v.first + bonusVertexIdOffset, v.second));
				}
			}
			return edges;
		}

		// a vertex that was reaches without bonus edge, so
		// every pair of edges is possible: either from the original 
		// graph or using the bonusEdge
		for (auto v : vertices_)
		{
			if (v == u) continue;
			auto edgeIt1 = edges_.find(u);
			if (edgeIt1 != edges_.end())
			{
				auto edgeIt2 = edgeIt1->second.find(v);
				if (edgeIt2 != edgeIt1->second.end())
				{
					// use original edge within g
					edges.push_back(Edge(v, edgeIt2->second));
					continue;
				}
			}
			// add bonus edge to g'
			edges.push_back(Edge(v + bonusVertexIdOffset, bonusEdgeWeight));
		}

		return edges;
	}
};

void printResult(int start, int end, int bonusWeight, const Path& path)
{
	std::cout << "shortes path from " << start << " to " << end 
		<< " with bonus edge weight " << bonusWeight << " is " << std::endl;
	std::cout << "  weight: " << path.first << std::endl;
	std::cout << "  path: ";
	for (auto v : path.second)
	{
		std::cout << v.first << (v.second ? "' " : " ");
	}
	std::cout << std::endl << std::endl;
}

int main()
{
	// sample 1
	Graph g1;
	g1.addEdge(1, 2, 2);
	g1.addEdge(2, 3, 1);
	g1.addEdge(2, 4, 2);
	g1.addEdge(3, 4, 3);
	printResult(1, 4, 5, g1.getShortestPathWithBonusEdge(1, 4, 5));

	Graph g2;
	g2.addEdge(1, 2, 2);
	g2.addEdge(1, 4, 4);
	g2.addEdge(2, 3, 1);
	g2.addEdge(3, 4, 3);
	g2.addEdge(4, 5, 1);
	printResult(1, 4, 2, g2.getShortestPathWithBonusEdge(1, 4, 2));

	/* Output
	shortes path from 1 to 4 with bonus edge weight 5 is
	weight: 4
	path: 1 2 4

	shortes path from 1 to 4 with bonus edge weight 2 is
	weight: 3
	path: 1 5' 4'
	*/
 }

I forgot to post the explanation of above algorithm:

The key idea is to dynamically extend the graph to a graph g'. When ever we are on a vertex in the original graph g, there are the edges given + to every other vertex where no edge was given there exists the "bonus edge" (with extra weight). Once used we are in g' and can't use the "bonus edge" anymore.That is, in g' there exist only the original edges to vertices in g but to their "mirror" in g'.

Visually, I drew the original graph g and on top a layer with the graph g'... Besides this I could use dijkstra. A vertex is identified with an integer in this solution. A vertex in g has an id below a certain value and a vertex in g' has just an offset to that id. There are certainly more apealing designs to that, but it did work and I could verify some basic cases.

Runtime is: Dijkstra but with V^2 edges. So O(E V * lg(V)) become O(V^3*lg(V)) ... not that sexy ... (E is the number of edges and V is the number of vertices)

could u please code this question in c language.Actually i dont know c++ much...@ ChrisZ

#include<cstdio>
#include<vector>
#include<climits>
#define min(a,b) (a<b?a:b)
#define MAXLEN 100
using namespace std;

int find_min(int dist[],bool visited[],int n)
{
    int i,mx,m;
    mx = INT_MAX;
    for(i=0;i<n;i++)
    {
        if(dist[i]<mx && !visited[i])
        {
            mx = dist[i];
            m = i;
        }
    }
    return m;
}

int find_res(int start,int target,int graph[][MAXLEN],int n)
{
    int u,v,w,dist[MAXLEN],cnt,i,j;
    bool visited[MAXLEN];

    for(i=0;i<n;i++)
    {
        dist[i] = INT_MAX;
        visited[i] = false;
    }

    dist[start] = 0;
    for(cnt = 1;cnt<n;cnt++)
    {
        u = find_min(dist,visited,n);
        visited[u] = true;
        for(v=0;v<n;v++)
        {
            if(graph[u][v]!=-1 && !visited[v] && dist[u]+graph[u][v]<dist[v])
            {
                dist[v] = dist[u] + graph[u][v];
            }
        }
    }
    return dist[target];
}

int minCost(int node,vector<int> from,vector<int> to,vector<int> wt,int start,int target,int weight)
{
    int res,graph[MAXLEN][MAXLEN],i,j;

    start--;
    target--;
    for(i=0;i<node;i++)
    {
        for(j=0;j<node;j++)
            graph[i][j] = -1;
    }
    for(i=0;i<from.size();i++)
    {
        from[i]--;
        to[i]--;
        graph[from[i]][to[i]] = graph[to[i]][from[i]] = wt[i];
    }

    res = find_res(start,target,graph,node);
   // printf("res = %d\n",res);
    for(i=0;i<node;i++)
    {
        for(j=0;j<node;j++)
        {
            if(graph[i][j]==-1)
            {
                graph[i][j] = weight;
                res = min(find_res(start,target,graph,node),res);
                graph[i][j] = -1;
            }
        }
    }
    return res;
}

int main()
{
    int node,edge,a,b,w,i,st,target;
    vector<int> to,from,wt;

    scanf("%d%d",&node,&edge);
    for(i=0;i<edge;i++)
    {
        scanf("%d%d%d",&a,&b,&w);
        to.push_back(a);
        from.push_back(b);
        wt.push_back(w);
    }

    scanf("%d%d%d",&st,&target,&w);
    printf("%d\n",minCost(node,from,to,wt,st,target,w));
    return 0;
}