fork download
copy 
  1. /*
  2. AUTHOR : Chandan Agrawal
  3. College : Poornima College of Engg. jaipur, Raj
  4. Mail : chandanagrawal23@gmail.com
  5. */
  6.  
  7. #include<bits/stdc++.h>
  8. #include<stdio.h>
  9. using namespace std;
  10.  
  11. #define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  12. #define MAX 2000050
  13.  
  14. #define ll long long
  15. #define ld long double
  16. #define lli long long int
  17.  
  18. #define pb emplace_back
  19. #define INF 100000000000
  20. #define mod 1000000007
  21.  
  22. // trignometric function always give value in Radians only
  23. #define PI acos(-1) //3.1415926535897932384626433832795028
  24. #define dsin(degree) sin(degree*(PI/180.0))
  25. #define dcos(degree) cos(degree*(PI/180.0))
  26. #define dtan(degree) tan(degree*(PI/180.0))
  27.  
  28. #define rsin(radian) sin(radian)
  29. #define rcos(radian) cos(radian)
  30. #define rtan(radian) tan(radian)
  31.  
  32. #define loop(i,n) for (lli i = 0; i < n; i++)
  33. #define loopitr(xt,vec) for (auto xt : vec)
  34. #define FOR(i,a,b) for (lli i = a; i < b; i+=1)
  35. #define loop_rev(i,n) for (lli i = n-1; i >= 0; i--)
  36. #define FOR_REV(i,a,b) for (lli i = a; i >= b; i--)
  37. #define itr :: iterator it
  38. #define WL(t) while(t --)
  39.  
  40. #define all(v) v.begin(),v.end()
  41. #define sz(x) int(x.size())
  42. #define F first
  43. #define S second
  44.  
  45. #define mii map<lli,lli>
  46. #define vi vector<lli>
  47. #define seti set<lli>
  48. #define pii pair<lli,lli>
  49.  
  50. #define gcd(a,b) __gcd((a),(b))
  51. #define lcm(a,b) (a/gcd(a,b))*b
  52. #define abs(x) ((x < 0)?-(x):x)
  53.  
  54. template <typename T>
  55. void print(T x){cout<<x<<endl;}
  56. template <typename T1, typename T2>
  57. void print2(T1 x,T2 y){cout<<x<<" "<<y<<endl;}
  58. template <typename T1, typename T2,typename T3>
  59. void print3(T1 x, T2 y,T3 z){cout<<x<<" "<<y<<" "<<z<<endl;}
  60.  
  61. #define scanarr(a,n) for(lli i=0;i<n;i++)    cin>>a[i];
  62. #define scanvector(a,n) for(lli i=0;i<n;i++){ lli x ; cin>>x; a.pb(x);}
  63.  
  64. #define printarr(a,n) for(lli i=0;i<n;i++)   cout<<a[i]<<" "; cout<<endl;
  65. #define printvector(vec) for(auto xt : vec) cout<<xt<<" ";    cout<<"\n";
  66. #define printset(st) for(auto xt : st) cout<<xt<<" ";    cout<<"\n";
  67.  
  68. #define FD(N) fixed<<setprecision(N)
  69.  
  70. #define endl '\n'
  71.  
  72. #define deb(x) cout<<#x<<" "<<x<<endl;
  73.  
  74. // chandan1,2
  75. void chandan1(){int y=1;return;}
  76. void chandan2(){
  77.         loop(i,10){
  78.         lli x=1;
  79.     }
  80.     return(chandan1());
  81. }
  82.  
  83.  
  84. /*
  85.  
  86. 1) Initialize distances of all vertices as infinite.
  87.  
  88. 2) Create an empty priority_queue pq.  Every item
  89.    of pq is a pair (weight, vertex). Weight (or 
  90.    distance) is used used as first item  of pair
  91.    as first item is by default used to compare
  92.    two pairs
  93.  
  94. 3) Insert source vertex into pq and make its
  95.    distance as 0.
  96.  
  97. 4) While either pq doesn't become empty
  98.     a) Extract minimum distance vertex from pq. 
  99.        Let the extracted vertex be u.
  100.     b) Loop through all adjacent of u and do 
  101.        following for every vertex v.
  102.  
  103.            // If there is a shorter path to v
  104.            // through u. 
  105.            If dist[v] > dist[u] + weight(u, v)
  106.  
  107.                (i) Update distance of v, i.e., do
  108.                      dist[v] = dist[u] + weight(u, v)
  109.                (ii) Insert v into the pq (Even if v is
  110.                     already there)
  111.                
  112. 5) Print distance array dist[] to print all shortest
  113.    paths. 
  114.    
  115.  
  116. */
  117.  
  118.  
  119.  
  120. // create adjacency list of pair 
  121. // adj[u].pb({v,cost}) from u to v cost is cost
  122.  
  123.  
  124.  
  125.  
  126. lli Dijikistra(vector<pii>adj[] , lli v , lli source , lli destin){
  127.  
  128.     lli dist[v+1] , parent[v+1];
  129.  
  130.     for(lli i=1;i<=v;i++)
  131.         dist[i] = INF;
  132.  
  133.     dist[source] = 0;
  134.  
  135.     // min priority queue of pair 
  136.     // where pair is < (cost from u to v)  , node >
  137.     priority_queue<pii , vector<pii> , greater<pii> > pq;
  138.  
  139.     pq.push(make_pair(0,source));    // from source to source cost is 0
  140.  
  141.     parent[source] = source;
  142.  
  143.  
  144.     while(!pq.empty()){
  145.  
  146.         lli u  = pq.top().S;
  147.  
  148.         pq.pop();
  149.  
  150.         for(auto xt : adj[u]){
  151.  
  152.             lli v = xt.F;
  153.  
  154.             lli weight = xt.S;
  155.  
  156.             if(dist[v] > (dist[u] + weight) )
  157.             {
  158.                dist[v] = dist[u] + weight;
  159.  
  160.                pq.push(make_pair(dist[v] , v));
  161.  
  162.                parent[v] = u;
  163.             }
  164.  
  165.         }
  166.  
  167.     }
  168.  
  169.     return dist[destin];
  170.  
  171. }
  172.  
  173.  
  174.  
  175.  
  176. int main(){
  177. fastio
  178. lli t=1;
  179. cin>>t;
  180. chandan2();
  181. while(t--) {
  182.     lli v,e;
  183.     cin>>v;
  184.     vector<pii>adj[v+1];
  185.     map<string ,lli>mp;
  186.     for(lli j=1;j<=v;j++){
  187.         string s;
  188.         cin>>s;
  189.         mp[s]=j;
  190.         cin>>e;
  191.         loop(i,e){
  192.             lli y,cost;
  193.             cin>>y>>cost;
  194.             adj[j].pb(make_pair(y,cost));
  195.             //adj[y].pb(make_pair(j,cost));
  196.         }
  197.     }
  198.  
  199.     lli k;
  200.     cin>>k;
  201.     loop(i,k){
  202.         string str1,str2;
  203.         cin>>str1>>str2;
  204.         lli src = mp[str1];
  205.         lli destin  = mp[str2];
  206.         print(Dijikistra(adj,v,src,destin));
  207.     }
  208.  
  209.   }
  210. return 0;
  211. }
Success #stdin #stdout 0s 4296KB
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/qE8ZGs
language:
C++14 (gcc 8.3)
created:
3 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!