Rain strikes and the roads are flooded, Mr X has to get home from work. Your task is to make sure he
returns home in the shortest time.
Consider the roads as a graph with crossings as nodes, and the path between two nodes as an edge. Assume
the graph is undirected and the nodes are numbered, 1 to V (V <= 50).
The input consists of :
1. An integer H on a line, this is the height of Mr X.
2. Two integers N and M on the next line, where, N is the number of edges in the graph. M is the
number of nodes in the graph.
3. A sequence of N lines each having 4 integers : C1 C2 T D where, C1, C2 are the nodes (or
crossings), T is the time it takes to go from C1 to C2. D is the water depth along the edge(or road)
from C1 to C2.
Note: The depth D has to be less than the height of Mr X for him to be able to take the road.
4. Two integers S and E indicating the node at which Mr X starts and where he is expected to go to,
respectively.
As output you have to give the shortest path starting at S, listing each vertex in the order and ending with E
that Mr X can take. Assume that there will be at least one way to reach the destination and that the shortest
path is unique.
Sample Input/Output
Input
5
10 7
1 2 10 4
1 4 6 3
1 5 8 2
2 3 2 1
3 7 1 2
2 6 1 3
4 6 4 4
6 7 2 5
5 4 2 6
5 7 6 1
1 7
Output
1 2 3 7
A simple Dijkstra's algorithm to find the shortest path between source node and destination node. Whenever the depth is greater than the height of the man, treat it as an invalid edge. Below is the lose implementation of the above. NOTE: Implementation could be done better by using adjacency list to represent the graph and using priority queue. Time complexity is O(Vlog(V) where, V is the number of vertices.
- Prakash May 27, 2012#include<iostream> #include<list> using namespace std; #define INFINITY 10000; int disjkstras(int **graph, int n, int source, int dest); int get_min_vertex(int *distance, int *visited, int n); int main() { int H; cin >> H; int E, N; cin >> E >> N; int **graph = new int*[N]; for(int i=0; i<N ; i++) { graph[i] = new int[N]; } for(int i=0; i<N; i++) { for(int j=0; j<N; j++) { if(i==j) { graph[i][j] = 0; } else { graph[i][j] = INFINITY; } } } while(E--) { int C1, C2, T, D; cin >> C1 >> C2 >> T >> D; if(D <= H) { graph[C1-1][C2-1] = graph[C2-1][C1-1] = T; } } int S, E_; cin >> S >> E_; disjkstras(graph, N, S-1, E_-1); } int disjkstras(int **graph, int n, int source, int dest) { int *min_distance = new int[n]; int *route = new int[n]; int *visited = new int[n]; for(int i=0; i<n; i++) { min_distance[i] = INFINITY; visited[i]=0; route[i] = -1; } min_distance[source] = 0; route[source] = source; for(int i=0; i<n ; i++) { int min_vertex = get_min_vertex(min_distance, visited, n); for(int j=0; j<n; j++) { if(min_distance[j] > (graph[min_vertex][j] + min_distance[min_vertex])) { min_distance[j] = graph[min_vertex][j] + min_distance[min_vertex]; route[j] = min_vertex; } } visited[min_vertex] = 1; } cout << "Minimum distance : " << min_distance[dest] << endl; cout << "Path is : " << endl; list<int> path; path.push_front(dest); for(int i=dest; ; ) { path.push_front(route[i]); if(route[i] == source) { break; } else { i = route[i]; } } list<int>::iterator it; for(it=path.begin(); it!=path.end(); it++) { cout << (*it+1) << " "; } delete[] route; delete[] min_distance; delete[] visited; } int get_min_vertex(int *distance, int *visited, int n) { int ret_val = -1; int min = INFINITY; for(int i=0; i<n; i++) { if((distance[i] < min) && (visited[i] == 0)) { min = distance[i]; ret_val = i; } } return(ret_val); }