fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. #include <stack>
  5. #include <tuple>
  6.  
  7. using namespace std;
  8.  
  9. int n, cnt, curTime, curCity, srt, tar, cas = 0;
  10. const int inf = 0x1f3f3f3f;
  11. vector<int> par, minTime;
  12. vector<bool> vis;
  13. vector<vector<pair<int, int>>> adj;
  14. stack<int> dir;
  15. priority_queue<pair<int, int>, vector<pair<int, int>>, 
  16.     greater<pair<int, int>>> sts;
  17.  
  18.  
  19. void returnRes(){
  20.     cout << "Case " << ++cas << ": Path =";
  21.     dir.push(tar);
  22.     while(dir.top() != srt){
  23.         dir.push(par[dir.top()]);
  24.     } while(!dir.empty()){
  25.         cout << " " << dir.top();
  26.         dir.pop();
  27.     } cout << "; " << minTime[tar] << " second delay\n";
  28. }
  29.  
  30. void dijkstra(){
  31.     curCity = srt, curTime = 0;
  32.     sts.push({curTime, curCity});
  33.     while(!sts.empty()){
  34.         tie(curTime, curCity) = sts.top();
  35.         sts.pop();
  36.         //cout << curTime << " " << curCity << endl;
  37.         if(vis[curCity]) continue;
  38.         vis[curCity] = true;
  39.         if(curCity == tar){
  40.             returnRes();
  41.             while(!sts.empty()) sts.pop();
  42.         } for(pair<int, int> & i : adj[curCity]){
  43.             if(minTime[i.second] > i.first + curTime){
  44.                 minTime[i.second] = i.first + curTime;
  45.                 par[i.second] = curCity;
  46.                 sts.push({minTime[i.second], i.second});
  47.             }
  48.         } 
  49.     } //cout << "no\n";
  50. }
  51.  
  52. int main(){
  53.     ios_base::sync_with_stdio(false);
  54.     cin.tie(nullptr), cout.tie(nullptr);
  55.     while(cin >> n){
  56.         if(n == 0) break;
  57.         par.assign(n + 1, -1), vis.assign(n + 1, false);
  58.         adj.assign(n + 1, vector<pair<int, int>> ());
  59.         minTime.assign(n + 1, inf);
  60.         for(int i = 1; i <= n; i++){
  61.             cin >> cnt;
  62.             while(cnt--){
  63.                 cin >> curCity >> curTime;
  64.                 adj[i].push_back({curTime, curCity});
  65.             } 
  66.         } cin >> srt >> tar;
  67.         //cout << srt << " " << tar << endl;
  68.         dijkstra();
  69.     } return 0;
  70. }
Success #stdin #stdout 0s 5288KB
comments (?)
stdin
copy 
5
2 3 3 4 6
3 1 2 3 7 5 6
1 4 5
0
1 4 7
2 4
2
1 2 5
1 1 6
1 2
7
4 2 5 3 13 4 8 5 18
2 3 7 6 14
1 6 6
2 3 5 5 9
3 6 2 7 9 4 6
1 7 2
0
1 7
0
stdout
copy 
Case 1: Path = 2 1 4; 8 second delay
Case 2: Path = 1 2; 5 second delay
Case 3: Path = 1 2 3 6 7; 20 second delay
https://ideone.com/uT0JBW
language:
C++14 (gcc 8.3)
created:
2 days 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!