fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. ll ans,i,j,graph[1001][1001];
  5. string name[1001];
  6. vector<ll> grap[1001];
  7. ll  dijk(ll start, ll cities, ll end)
  8. {
  9. 	ll dis[cities+1];
  10. 	for(i=0;i<cities+1;i++)
  11. 	{
  12. 		dis[i]=INT_MAX;
  13. 	}
  14. 	dis[start]=0;
  15. 	vector <ll> set;
  16. 	set.push_back(start);
  17. 	bool visited[cities+1];
  18. 	for(i=0;i<=cities;i++)
  19. 	{
  20. 		visited[i]=false;
  21. 	}
  22. 	visited[start]=true;
  23. 	ll req=start;
  24. 	while(set.size()!=cities)
  25. 	{
  26. 		for(i=0;i<grap[req].size();i++)
  27. 		{
  28. 			dis[grap[req][i]]=min(dis[grap[req][i]], dis[req]+graph[req][grap[req][i]]);
  29. 		}
  30. 		ll reqans=INT_MAX;
  31. 		for(i=1;i<=cities;i++)
  32. 		{
  33. 			if(visited[i]==false)
  34. 			{
  35. 				if(dis[i]<reqans)
  36. 				{
  37. 					reqans=dis[i];
  38. 					req=i;
  39. 					visited[req]=true;
  40. 					set.push_back(i);
  41. 				}
  42. 			}
  43. 		}
  44. 	}
  45. 	ans=dis[end];
  46. 	return ans;
  47. }
  48. int main()
  49. {
  50. 	ll t;
  51. 	cin>>t;
  52. 	while(t--)
  53. 	{
  54. 		ll neigh,cities;
  55. 		cin>>cities;
  56. 		map<string, ll> city_index;
  57. 		for(i=0;i<1001;i++)
  58. 		{
  59. 			for(j=0;j<1001;j++)
  60. 			{
  61. 				graph[i][j]=INT_MAX;
  62. 			}
  63. 		}
  64. 		for(i=1;i<=cities;i++)
  65. 		{
  66. 			cin>>name[i];
  67. 			city_index[name[i]]=i;
  68. 			cin>>neigh;
  69. 			grap[i].resize(0);
  70. 			for(j=0;j<neigh;j++)
  71. 			{
  72. 				ll index,cost;
  73. 				cin>>index>>cost;
  74. 				graph[i][index]=cost;
  75. 				grap[i].push_back(index);
  76. 			}
  77. 		}
  78. 		ll queries;
  79. 		cin>>queries;
  80. 		while(queries--)
  81. 		{
  82. 			string start,end;
  83. 			cin>>start>>end;
  84. 			ll star,en;
  85. 			star=city_index[start];
  86. 			en=city_index[end];
  87. 			cout<<dijk(star,cities,en)<<endl;
  88. 		}
  89. 	}
  90. 	return 0;
  91. }
Success #stdin #stdout 0s 11128KB
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/hi2xQJ
language:
C++ (gcc 8.3)
created:
8 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!