fork(2) download 
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <vector>
  4. #include <queue>
  5. #include <cstring>
  6. #include <string>
  7. #include <map>
  8.  
  9. #define pp pair<int,int>
  10. #define MAX_D 1000000001
  11. #define N 10000
  12.  
  13. using namespace std;
  14.  
  15. class Prioritize
  16. {
  17. public:
  18.     int operator() ( const pair<int, int>& p1, const pair<int, int>& p2 )
  19.     {
  20.         return p1.second > p2.second;
  21.     }
  22. };
  23.  
  24. bool visited[N+1];
  25.  
  26. char city[15],startCity[15],destCity[15];
  27. int main()
  28. {
  29.         int t,i,j,queries;
  30.         scanf("%d",&t);
  31.         while(t--)
  32.         {
  33.                 priority_queue<pp, vector<pp > , Prioritize > Q;
  34.                 map<string,int>myMap;
  35. 				map<string,int>:: iterator it;
  36.                 int n,e;
  37.                 int u,v,w;
  38.                 scanf("%d",&n);
  39.                 vector< pp > G[n+1];
  40.  
  41.                 for(i=1;i<=n;i++)
  42.                 {
  43. 					scanf("%s",city);
  44. 					myMap.insert(pair<string,int>(city,i));
  45. 					scanf("%d",&e);
  46. 					for(j=1;j<=e;j++)
  47. 					{
  48.                         scanf("%d %d",&v,&w);
  49.                         G[i].push_back(pp(v,w));
  50. 					}
  51. 				}
  52.                 int s,dest;
  53.                 int d[n+1];
  54. 				for(int i=1;i<=n;i++)
  55. 				{
  56.                      d[i] = MAX_D;
  57.                      visited[i]=false;
  58. 				}
  59.                 scanf("%d",&queries);
  60.                 while(queries--)
  61.                 {
  62. 					scanf("%s %s",startCity,destCity);
  63.  
  64. 					it=myMap.find(startCity);
  65. 					s=it->second;
  66.  
  67. 					it=myMap.find(destCity);
  68. 					dest=it->second;
  69.  
  70.  
  71. 					d[s] = 0;
  72. 					Q.push(pp(s,d[s]));
  73. 					while(!Q.empty())
  74. 					{
  75. 							u = Q.top().first;
  76. 							w = Q.top().second;
  77.  
  78. 							if(u==dest)break; /*as only shortest distance to one point is desired */
  79. 							if(visited[u])continue;
  80. 							Q.pop();
  81. 							if(w > d[u]) continue;
  82.  
  83. 							int size = G[u].size();
  84. 							for(int i = 0 ; i < size ; i++)
  85. 							{
  86. 									v = G[u][i].first;
  87. 									w = G[u][i].second;
  88. 									if(!visited[v] && (d[v] > d[u] + w))
  89. 									{
  90. 											d[v] = d[u] + w;
  91. 											Q.push(pp(v,d[v]));
  92. 									}
  93. 							}
  94.  
  95. 					}
  96. 					printf("%d\n",d[dest]);
  97. 				}
  98. 		}
  99.                 return 0;
  100. }
  101.  
Success #stdin #stdout 0s 3488KB
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/hB5rQ2
language:
C++ (gcc 8.3)
created:
11 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!