fork(1) 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,vector<int>&);
  23. };
  24. int Graph::dijkstra(int a,int b,vector<int>&vec)
  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.     for(i=1;i<=v;i++){
  51.         vec.push_back(dist[i]);
  52.     }
  53.     return dist[b];
  54. }
  55. int main()
  56. {
  57.     int n,tc,p,nr,i,j,k,no_of_paths,cost;
  58.     string name,name1,name2;
  59.     map<string,int> mp1;
  60.     cin>>tc;
  61.     for(i=0;i<tc;i++){
  62.         cin>>n;
  63.         Graph g(n);
  64.         for(j=1;j<=n;j++){
  65.             cin>>name;
  66.             mp1[name]=j;
  67.             cin>>p;
  68.             for(k=0;k<p;k++){
  69.                 cin>>nr>>cost;
  70.                 g.addEdge(j,nr,cost);
  71.             }
  72.         }
  73.         cin>>no_of_paths;
  74.         vector<int> store[no_of_paths+1];
  75.         for(k=0;k<no_of_paths;k++){
  76.             cin>>name1>>name2;
  77.             if(store[mp1[name1]].size()!=0){
  78.                 cout<<store[mp1[name1]][mp1[name2]-1]<<endl;
  79.                 continue;
  80.             }
  81.             cout<<g.dijkstra(mp1[name1],mp1[name2],store[mp1[name1]])<<endl;
  82.         }
  83.     }
  84.     return 0;
  85. }
  86.  
Success #stdin #stdout 0s 4392KB
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/MQ3yTa
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!