fork(1) download 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int main()
  6. {
  7.  
  8.     int testcases;
  9.     cin >> testcases;
  10.     while(testcases-->0)
  11.     {
  12.         int cities;
  13.         cin >> cities;
  14.         string arr[cities+1];
  15.         vector<pair<int,int>> adjacencylist[cities+1]; // --->> see +1 added
  16.         unordered_map<string,int> mymap;
  17.         for(int i=1;i<=cities;i++)
  18.         {
  19.             cin >> arr[i];
  20.             mymap[arr[i]]=i;
  21.             int temp;
  22.             cin >> temp;
  23.             while(temp-->0)
  24.             {
  25.                 int nr,cost;
  26.                 cin >> nr >> cost;
  27.                 adjacencylist[i].push_back(pair<int,int>(cost,nr));  // -->> crash , because i==cities, but adjacencylist doesnot have cities index.
  28.             }
  29.         }
  30.         int xx;
  31.         cin >> xx;
  32.         while(xx-->0)
  33.         {
  34.             string source,destination;
  35.         cin >>  source >> destination;
  36.         int index1=mymap[source],index2=mymap[destination];
  37.         int dist[cities+1];
  38.         for(int i=1;i<=cities;i++)
  39.         {
  40.             dist[i]=10000;
  41.         }
  42.         dist[index1]=0;
  43.         priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> myqueue;
  44.         myqueue.push(pair<int,int>(dist[index1],index1));
  45.         while(myqueue.size())
  46.         {
  47.             pair<int,int> p=myqueue.top();
  48.             myqueue.pop();
  49.             //cout << "extracted min " << p.second << " ans distance of it is " << p.first << endl;
  50.  
  51.             //---->> see need check valid or not p element
  52.             if (dist[p.second] != p.first )
  53.                 continue;
  54.             //------------------------------------------------
  55.             for(pair<int,int> vv : adjacencylist[p.second])
  56.             {
  57.                 if(dist[vv.second]>dist[p.second]+vv.first)
  58.                 {
  59.                     dist[vv.second]=p.first+vv.first;
  60.                    // cout << "pushing " << vv.second << " vertex ans its distance is " << dist[vv.second] << endl;
  61.                     myqueue.push(pair<int,int>(dist[vv.second],vv.second));
  62.                 }
  63.             }
  64.         }
  65.         cout << dist[index2] << endl;
  66.         }
  67.  
  68.     }
  69. }
  70.  
Success #stdin #stdout 0s 3480KB
comments (?)
stdin 
1
4
gdansk
2
2 1
3 3
bydgoszcz
3
1 1
3 1
4 4
torun
3
1 3
2 1
4 1
warszawa
2
2 4
3 1
2
gdansk warszawa
bydgoszcz warszawa
stdout 
3
2
https://ideone.com/wovGYJ
language:
C++14 (gcc 8.3)
created:
7 years 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!