fork download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define MAX 10000000
  4. typedef pair<int, int> pi;
  5. class Graph
  6. {
  7. private:
  8.     int v;
  9.     list<int>* adj;
  10.     map<pair<int,int>,int> mp;
  11. public:
  12.     Graph(int n)
  13.     {
  14.         v=n;
  15.         adj=new list<int> [v+1];
  16.     }
  17.     void addEdge(int a,int b,int w)
  18.     {
  19.         adj[a].push_back(b);
  20.         mp[{a,b}]=w;
  21.     }
  22.     int dijkstra(int,int);
  23. };
  24. int Graph::dijkstra(int a,int b)
  25. {
  26.     int i,j,u,temp;
  27.     priority_queue<pi, vector<pi>, greater<pi> > pq;
  28.     int dist[v+1],visited[v+1]={};
  29.     for(i=1;i<=v;i++){
  30.         dist[i]=MAX;
  31.     }
  32.     dist[a]=0;
  33.     pq.push(make_pair(0,a));
  34.     list<int>::iterator it;
  35.     while(!pq.empty()){
  36.         //u=extract_min(visited,dist,v);
  37.         u=pq.top().second;
  38.         pq.pop();
  39.         visited[u]=1;
  40.         for(it=adj[u].begin();it!=adj[u].end();it++){
  41.             //relax(u,*it,mp[{u,*it}],dist);
  42.             temp=dist[u]+mp[{u,*it}];
  43.             if(dist[*it]>temp){
  44.                 dist[*it]=temp;
  45.                 if(visited[*it]==0)
  46.                     pq.push(make_pair(temp,*it));
  47.             }
  48.         }
  49.     }
  50.     return dist[b];
  51. }
  52. int main()
  53. {
  54.     int n,tc,p,nr,i,j,k,no_of_paths,cost;
  55.     string name,name1,name2;
  56.     map<string,int> mp1;
  57.     cin>>tc;
  58.     for(i=0;i<tc;i++){
  59.         cin>>n;
  60.         Graph g(n);
  61.         for(j=1;j<=n;j++){
  62.             cin>>name;
  63.             mp1[name]=j;
  64.             cin>>p;
  65.             for(k=0;k<p;k++){
  66.                 cin>>nr>>cost;
  67.                 g.addEdge(j,nr,cost);
  68.             }
  69.         }
  70.         cin>>no_of_paths;
  71.         for(k=0;k<no_of_paths;k++){
  72.             cin>>name1>>name2;
  73.             cout<<g.dijkstra(mp1[name1],mp1[name2])<<endl;
  74.         }
  75.     }
  76.     return 0;
  77. }
  78.  
Success #stdin #stdout 0s 4528KB
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/bp7KEk
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

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!