|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 |
#include <iostream> #include <stdio.h> #include <vector> #define inf 1000000000 using namespace std; vector<int> v; int path[11][11]; int NExt[11][11]; bool first; /* void find_path(int a,int b) { v.push_back(b); while(NExt[a][b]!=-1) { v.push_back(NExt[a][b]); b=NExt[a][b]; } v.push_back(a); } */ void find_path(int i,int j) { if(NExt[i][j]==-1) if(first) { cout<<i<<" "<<j; first=false; } else { cout<<" "<<j; } else { find_path(i,NExt[i][j]); find_path(NExt[i][j],j); } } int main() { int NI; int intersection; int start,end,a,b,c=1; while(cin>>NI) { if(NI==0) break; first=true; for(int i=0;i<11;i++) { for(int j=0;j<11;j++) { path[i][j]=inf; NExt[i][j]=-1; } } for(int i=1;i<=NI;i++) { cin>>intersection; for(int j=1;j<=intersection;j++) { cin>>a>>b; path[i][a]=b; } } cin>>start>>end; for(int i=1;i<=NI;i++) { for(int j=1;j<=NI;j++) { for(int k=1;k<=NI;k++) { if(path[j][i]!=inf && path[i][k]!=inf && (path[j][i]+path[i][k])<=path[j][k]) { path[j][k]=(path[j][i]+path[i][k]); NExt[j][k]=i; } } } } //v.clear(); cout<<"Case "<<c++<<": Path = "; find_path(start,end); /*for(int i=v.size()-1;i>=0;i--) { cout<<v[i]; if(i) cout<<" "; else cout<<"; "; }*/ cout<<"; "<<path[start][end]<<" second delay\n"; } return 0; } |
This problem can also be solved using Dijkstra’s algorithm.
The one thing to keep in mind is to store the parent vertex of any vertex, so that we can reconstruct the path once we reached the target node. To remember the path, we can use a vector to store where I con from in some vertex. And use the function printPath to print that vector backwards. Here is the printPath function [solution taken from another source.]
|
1 2 3 4 5 6 7 8 |
void printPath(int t) { if (t == s) printf("%d", s+1); else { printPath(p[t]); printf(" %d", t+1); } } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 |
#include <cstdio> #include <vector> #include <queue> #include <functional> #define INF 1e9 using namespace std; typedef vector<int> vi; typedef pair<int, int> ii; typedef vector<ii> vii; vi p; int dist[10]; vector<vii> AdjList; int c, V, b, w, s, t, cas=1; priority_queue<ii, vector<ii>, greater<ii> > pq; void printPath(int t) { if (t == s) printf("%d", s+1); else { printPath(p[t]); printf(" %d", t+1); } } void init() { for (int i=0 ; i<10 ; i++) dist[i] = INF; } int dijkstra() { pq = priority_queue<ii, vector<ii>, greater<ii> >(); init(); pq.push(ii(0, s)); dist[s] = 0; while (!pq.empty()) { ii front = pq.top(); pq.pop(); int d=front.first, u=front.second; if (u == t) return d; if (dist[u] == d) { for (int i=0 ; i<AdjList[u].size() ; i++) { ii v = AdjList[u][i]; if (dist[u] + v.second < dist[v.first]) { dist[v.first] = dist[u] + v.second; p[v.first] = u; pq.push(ii(dist[v.first], v.first)); } } } } } int main() { while (scanf("%d", &V), V) { AdjList.assign(V, vii()); for (int i=0 ; i<V ; i++) { scanf("%d", &c); while (c--) { scanf("%d %d", &b, &w); b--; AdjList[i].push_back(ii(b, w)); } } p.assign(V, 0); scanf("%d %d", &s, &t); s--, t--; dijkstra(); printf("Case %d: Path = ", cas++); printPath(t); printf("; %d second delay\n", dist[t]); } } |