fork(1) download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <cstdio>
  4. #include <map>
  5. #include <set>
  6. #include <string>
  7. #include <algorithm>
  8. using namespace std;
  9.  
  10. const int maxn = 10010, inf = 800000;
  11.  
  12. vector <int> D(maxn);
  13. vector < vector < pair<int,int> > > graph(maxn);
  14. map <string,int> getByName;
  15. int n;
  16.  
  17. void update()
  18. {
  19.  
  20. }
  21.  
  22. int dijkstra(int start, int end)
  23. {
  24. 	set < pair <int,int> > Q;
  25. 	D[start] = 0;
  26.  
  27. 	Q.insert( make_pair( D[start], start ) );
  28.  
  29. 	while( Q.empty() == false )
  30. 	{
  31. 		pair <int,int> pr = *Q.begin();
  32. /*		
  33. 		if( pr.second == end )
  34. 			return pr.first;
  35. */
  36. 		Q.erase( Q.begin() );
  37.  
  38. 		for( vector < pair<int,int> >::iterator it = graph[ pr.second ].begin(); it != graph[ pr.second ].end(); it++ )
  39. 		{
  40. 			int to = it->first, cost = it->second;
  41.  
  42. 			if( D[to] > D[ pr.second ] + cost )
  43. 			{
  44. 				if( D[to] != inf )
  45. 					Q.erase( Q.find( make_pair( D[to], to ) ) );
  46. 				D[to] = D[ pr.second ] + cost;
  47. 				Q.insert( make_pair( D[to], to ) );
  48. 			}
  49. 		}
  50. 	}
  51. 	return D[end];
  52. }
  53.  
  54. void SHPATH()
  55. {
  56. 	getByName.clear();
  57. 	graph.clear();
  58. 	graph.resize(maxn);
  59.  
  60. 	int i, j, to, w, a, b, c, n1;
  61. 	string str, str1;
  62. 	char name[25], name1[25];
  63.  
  64. 	scanf("%d", &n);
  65.  
  66. 	for(i = 0; i < n; ++i)
  67. 	{
  68. 		scanf("%s", &name); str = name;
  69. 		getByName[ str ] = i;
  70.  
  71. 		scanf("%d", &n1);
  72. 		for(j = 0; j < n1; ++j)
  73. 		{
  74. 			scanf("%d%d", &to, &w);
  75. 			graph[i].push_back( make_pair( to-1, w ) );
  76. 		}
  77. 	}
  78.  
  79. 	scanf("%d", &n1);
  80. 	for(i = 0; i < n1; ++i)
  81. 	{
  82. 		D.clear();
  83. 		D.resize(maxn,inf);
  84.  
  85. 		scanf("%s" , &name);
  86. 		scanf("%s" , &name1);
  87.  
  88. 		str = name;
  89. 		str1 = name1;
  90.  
  91. 		a = getByName[ str ];
  92. 		b = getByName[ str1 ];
  93. 		c = dijkstra(a, b);
  94.  
  95. 		printf("%d\n", c); 
  96.  
  97. 	}
  98. }
  99.  
  100. int main()
  101. {
  102. 	int testcase;
  103. 	scanf("%d", &testcase);
  104.  
  105. 	while( testcase-- )
  106. 		SHPATH();
  107.  
  108. 	return 0;
  109. }
Success #stdin #stdout 0s 3488KB
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/mRPwup
language:
C++ (gcc 8.3)
created:
10 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!