fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2. #define pii pair<int,int>
  3. #define s(x) scanf("%d",&x)
  4. #define INF (1<<20)
  5. #define MAX 10000
  6. using namespace std;
  7. int d[MAX+5];
  8. vector<pii> G[MAX];
  9. struct comp {
  10.     //priority queue has priority according to distance
  11.     bool operator() (const pii &a, const pii &b) {
  12.         return a.second > b.second;
  13.     }
  14. };
  15. void addedge(int u, int v, int w)
  16. {
  17.     G[u].push_back(make_pair(v,w));
  18. }
  19. void dijkstra(int root,int des)
  20. {
  21.     d[root]=0;
  22.     int u,v,w;
  23.     vector<pii> :: iterator it;
  24.     priority_queue<pii,vector<pii>,comp> Q;
  25.     Q.push(pii(root,0));
  26.     while(!Q.empty())
  27.     {
  28.         u=Q.top().first;
  29.         if(u==des)
  30.             break;
  31.         Q.pop();
  32.         for(it=G[u].begin(); it!=G[u].end(); it++)
  33.         {
  34.             v=(*it).first;
  35.             w=(*it).second;
  36.             if(d[v]>d[u]+w)
  37.             {
  38.                 d[v]=d[u]+w;
  39.                 Q.push(pii(v,d[v]));
  40.             }
  41.  
  42.         }
  43.  
  44.     }
  45.  
  46. }
  47. int main()
  48. {
  49.     int t,n,p,nr,cost,t1;
  50.     map<string,int> m;
  51.     string s,s1,s2;
  52.     s(t);
  53.     while(t--)
  54.     {
  55.         s(n);
  56.  
  57.         for(int i=0; i<n; i++)
  58.         {
  59.             cin>>s;
  60.             m.insert(make_pair(s,i));
  61.             s(p);
  62.             while(p--)
  63.             {
  64.                 s(nr);
  65.                 s(cost);
  66.                 addedge(i,nr-1,cost);
  67.             }
  68.  
  69.         }
  70.         s(t1);
  71.         while(t1--)
  72.         {
  73.             cin>>s1>>s2;
  74.             dijkstra(m[s1],m[s2]);
  75.             cout<<d[m[s2]]<<endl;
  76.             for(int i=0; i<n; i++)
  77.             d[i]=INF;
  78.         }
  79.         m.clear();
  80.         for(int i=0; i<n; i++)
  81.             G[i].clear();
  82.     }
  83.     return 0;
  84. }
  85.  
Time limit exceeded #stdin #stdout 5s 265792KB
comments (?)
stdin
copy 
2
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
1
4
A
1
2 2
B
1
3 3
C
2
2 1
4 3
D
0
stdout
copy 
0
2
https://ideone.com/AMFY75
language:
C++ (gcc 8.3)
created:
9 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!