fork download
copy 
  1. #include <iostream>
  2. #include <utility>
  3. #include <set>
  4. #include <vector>
  5. #include <string>
  6. #include <map>
  7. using namespace std;
  8. typedef int btype; //basic type to be used overall
  9. typedef pair<btype,btype> pii;
  10. typedef vector<pii> vpii;
  11. typedef vector<vpii> vvpii;
  12. #define INF 99999999
  13.  
  14. btype dijkstra(const vvpii &G, btype start, btype target)
  15. {
  16.     //vector to store keys
  17.     vector<btype> keys(G.size(),INF); //initialize all keys with INF
  18.     keys[start] = 0; //initialize key of start as 0
  19.     //NOW MAKE HEAP,we use set for heap using its property as its a red-blk tree implementation
  20.     set <pii> Q;
  21.     btype i;
  22.     for(i = 1;i<=G.size();i++) //PUT ALL VERTICES IN HEAP
  23.     {
  24.         if(i!=start)
  25.             Q.insert({INF,i});
  26.     }
  27.     Q.insert({0,start}); //{key,vertex} is a pair
  28.     while(!Q.empty())
  29.     {
  30.         pii top = *(Q.begin()); //EXTACT-MIN
  31.         btype u = top.second, key = top.first;
  32.         Q.erase(Q.begin()); //DELETE-MIN
  33.  
  34.         if(u == target) //REACHED THE DESTINATION
  35.             break;
  36.         //FOR ALL NEIGHBOURS, PERFORM RELAX
  37.         for(vpii::const_iterator it = G[u].begin(); it != G[u].end(); it++)
  38.         {
  39.             btype v= (*it).first,cost = (*it).second; //edge cost
  40.  
  41.             if(key + cost < keys[v]) //RELAX if relaxation can be done
  42.             {
  43.  
  44.                 Q.erase(Q.find({keys[v],v}));
  45.                 keys[v] = key + cost;
  46.                 Q.insert({keys[v],v});
  47.             }
  48.  
  49.         }
  50.     }
  51.     return keys[target];
  52. }
  53. int main()
  54. {
  55.     int t;
  56.     ios::sync_with_stdio(false);
  57.     cin>>t;
  58.     while(t--)
  59.     {
  60.         map <string,int> nametoindex;
  61.         btype i,j,n;
  62.         btype u,v,w,neighbours;
  63.         string name;
  64.         //GRAPH INPUT
  65.         cin>>n;
  66.  
  67.         vvpii G(n+1,vpii()); //0 --> n cities
  68.  
  69.         for(u=1;u<=n;u++)
  70.         {
  71.             //G.push_back(vpii());
  72.             cin>>name;
  73.             cin>>neighbours;
  74.  
  75.             nametoindex[name] = u;
  76.  
  77.             for(j=1;j<=neighbours;j++)
  78.             {
  79.                 cin>>v>>w;
  80.                 G[u].push_back(make_pair(v,w));
  81.             }
  82.         }
  83.         //GRAPH INPUT COMPLETED
  84.         //DIJ INPUT
  85.         cin>>n;//no of queries
  86.         string start,target;
  87.         for(i=1;i<=n;i++)
  88.         {
  89.             cin>>start>>target;
  90.             u = nametoindex[start];
  91.             v = nametoindex[target];
  92.             cout<<dijkstra(G,u,v)<<"\n";
  93.         }
  94.     }
  95.  
  96.     return 0;
  97. }
  98.  
Success #stdin #stdout 0s 3416KB
comments (?)
stdin
copy 
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
copy 
3
2
https://ideone.com/Ip8Kzf
Dijkstra's (SHPATH)
language:
C++14 (gcc 8.3)
created:
8 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!