fork download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define MAX 500000
  4. typedef pair<int, int> pi;
  5. class Graph
  6. {
  7. private:
  8.     int v;
  9.     vector<pair<int,int>>* adj;
  10. public:
  11.     Graph(int n)
  12.     {
  13.         v=n;
  14.         adj=new vector<pair<int,int>> [v+1];
  15.     }
  16.     void addEdge(int a,int b,int w)
  17.     {
  18.         adj[a].push_back({b,w});
  19.     }
  20.     int dijkstra(int,int,vector<int>&);
  21. };
  22. int Graph::dijkstra(int a,int b,vector<int>&vec)
  23. {
  24.     int i,j,u,temp,flag,it,siez;
  25.     priority_queue<pi,vector<pi>,greater<pi>> pq;
  26.     int dist[v+1];
  27.     bool visited[v+1];
  28.     for(i=1;i<=v;i++){
  29.         dist[i]=MAX;
  30.         visited[i]=false;
  31.     }
  32.     dist[a]=0;
  33.     pq.push(make_pair(0,a));
  34.     while(!pq.empty()){
  35.         u=pq.top().second;
  36.         pq.pop();
  37.         visited[u]=true;
  38.         for(it=0;it<adj[u].size();it++){
  39.                 flag=adj[u][it].first;
  40.                 siez=adj[u][it].second;
  41.             temp=dist[u]+siez;
  42.             if(dist[flag]>temp){
  43.                 dist[flag]=temp;
  44.                 if(visited[flag]==false)
  45.                     pq.push(make_pair(temp,flag));
  46.             }
  47.         }
  48.     }
  49.     for(i=1;i<=v;i++){
  50.         vec.push_back(dist[i]);
  51.     }
  52.     return dist[b];
  53. }
  54. int main()
  55. {
  56.     int n,tc,p,nr,i,j,k,no_of_paths,cost;
  57.     string name,name1,name2;
  58.     map<string,int> mp1;
  59.     ios_base::sync_with_stdio(false);
  60.     cin.tie(NULL);
  61.     cin>>tc;
  62.     for(i=0;i<tc;i++){
  63.         cin>>n;
  64.         Graph g(n);
  65.         for(j=1;j<=n;j++){
  66.             cin>>name;
  67.             mp1[name]=j;
  68.             cin>>p;
  69.             for(k=0;k<p;k++){
  70.                 cin>>nr>>cost;
  71.                 g.addEdge(j,nr,cost);
  72.             }
  73.         }
  74.         cin>>no_of_paths;
  75.         vector<int> store[no_of_paths+1];
  76.         for(k=0;k<no_of_paths;k++){
  77.             cin>>name1>>name2;
  78.             if(store[mp1[name1]].size()!=0){
  79.                 cout<<store[mp1[name1]][mp1[name2]-1]<<endl;
  80.                 continue;
  81.             }
  82.             cout<<g.dijkstra(mp1[name1],mp1[name2],store[mp1[name1]])<<endl;
  83.         }
  84.     }
  85.     return 0;
  86. }
  87.  
Success #stdin #stdout 0s 4540KB
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/74qnEC
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!