fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. #define int long long
  5. #define endl "\n"
  6.  
  7. void dij(int src, int dest, int n, vector<vector<pair<int,int>>> &adj, vector<int> &path, vector<int> &dist, vector<int> &par){
  8. 	priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
  9. 	pq.push({0, src});
  10.  
  11. 	while (!pq.empty()) {
  12.         int u = pq.top().second;
  13.         int d = pq.top().first;
  14.         pq.pop();
  15.  
  16.         if (u == dest) break;
  17.  
  18.         if (d > dist[u]) continue;
  19.  
  20.         for(int i = 0; i < adj[u].size(); i++) {
  21.  
  22.             int v = adj[u][i].first;
  23.             int weight = adj[u][i].second;
  24.  
  25.             if (dist[u] + weight < dist[v]) {
  26.                 dist[v] = dist[u] + weight;
  27.                 par[v] = u;
  28.                 pq.push({dist[v], v});
  29.             }
  30.         }
  31.     }
  32. }
  33.  
  34. signed main(){
  35. 	ios_base::sync_with_stdio(0);
  36.     cin.tie(0);cout.tie(0);
  37.     int tc = 0, n;
  38.     while(cin >> n && n != 0){
  39.     	tc++;
  40.     	vector<vector<pair<int,int>>> adj(n + 1);
  41.     	vector<int> path;
  42.     	vector<int> dist(n + 1, INT_MAX);
  43.     	vector<int> par(n + 1, -1); 
  44.  
  45.     	for(int i = 1; i <= n; i++){
  46.     		int t; cin >> t;
  47.     		for(int j = 1; j <= t; j++){
  48.     			int b,w;
  49.     			cin >> b >> w;
  50.     			adj[i].push_back({b,w});
  51. 			}
  52. 		}
  53.  
  54. 		int u,v; cin >> u >> v;
  55. 		dist[u] = 0;
  56.  
  57. 		dij(u,v,n,adj,path,dist,par);
  58.  
  59. 		cout << "Case " << tc <<": Path =";
  60. 		int i = v;
  61. 		while(i != u){
  62. 			path.push_back(i);
  63. 			i = par[i];
  64. 		}
  65. 		path.push_back(u);
  66.  
  67. 		for(int i = path.size() - 1; i >= 0; i--){
  68. 			cout << ' ' << path[i];
  69. 		}
  70.  
  71. 		cout << "; " << dist[v] << " second delay" << endl;
  72. 	}
  73. }
  74.  
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
8
2 2 9 8 10
1 3 9
1 4 9
1 5 9
1 6 9
1 7 9
1 8 9
0
1 8

0
stdout
copy 
Case 1: Path = 1 8; 10 second delay
https://ideone.com/YnEGWx
language:
C++ (gcc 8.3)
created:
4 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!