fork download 
  1. #include <bits/stdc++.h> 
  2. using namespace std;
  3.  
  4. const int INF = 1e9+7;
  5. const long long INFLL = 1e18+7;
  6. const int MAXN = 1e5+7;
  7.  
  8. int n,m,k;
  9. vector<int> pos[57];
  10. vector<pair<int,long long>> g[MAXN];
  11. long long Dist[57][MAXN];
  12. bool Check[MAXN];
  13.  
  14. void Dijkstra(int k)
  15. {
  16. 	fill(Dist[k]+1,Dist[k]+n+1,INFLL);
  17. 	memset(Check,0,sizeof Check);
  18. 	priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
  19. 	for (int x : pos[k])
  20. 	{
  21. 		Dist[k][x] = 0;
  22. 		pq.emplace(0,x);
  23. 	}
  24.  
  25. 	while (!pq.empty())
  26. 	{
  27. 		pair<long long, int> tp = pq.top();
  28. 		pq.pop();
  29. 		int u = tp.second;
  30. 		if (Check[u]) continue;
  31. 		Check[u] = 1;
  32.  
  33. 		for (pair<int,long long> x : g[u])
  34. 		{
  35. 			if (Dist[k][x.first] > Dist[k][u] + x.second)
  36. 			{
  37. 				Dist[k][x.first] = Dist[k][u] + x.second;
  38. 				pq.emplace(Dist[k][x.first],x.first);
  39. 			}
  40. 		}
  41. 	}
  42. }
  43.  
  44. int main()
  45. {
  46.   ios_base::sync_with_stdio(false);
  47.   cin.tie(nullptr);
  48.  
  49. 	cin >> n >> m >> k;
  50. 	for (int i = 1; i <= n; i++)
  51. 	{
  52. 		int ingre;
  53. 		cin >> ingre;
  54. 		pos[ingre].push_back(i);
  55. 	}
  56.  
  57. 	for (int i = 1; i <= m; i++)
  58. 	{
  59. 		int u,v;
  60. 		long long w;
  61. 		cin >> u >> v >> w;
  62. 		g[u].emplace_back(v,w);
  63. 		g[v].emplace_back(u,w);
  64. 	}
  65.  
  66. 	for (int i = 1; i <= k; i++)
  67. 		Dijkstra(i);
  68.  
  69. 	// for (int i = 1; i <= k; i++)
  70. 	// {
  71. 	// 	for (int j = 1; j <= n; j++)
  72. 	// 		cout << Dist[i][j] << '\t';
  73. 	// 	cout << '\n';
  74. 	// }
  75.  
  76. 	long long res = INFLL;
  77. 	int pos = 0;
  78. 	for (int i = 1; i <= n; i++)
  79. 	{
  80. 		long long tmp = 0;
  81. 		for (int j = 1; j <= k; j++)
  82. 		{
  83. 			if (Dist[j][i] == INFLL)
  84. 			{
  85. 				tmp = INFLL;
  86. 				break;
  87. 			}
  88. 			tmp+=Dist[j][i];
  89. 		}
  90. 		if (res > tmp)
  91. 		{
  92. 			pos = i;
  93. 			res = tmp;
  94. 		}
  95. 	}
  96.  
  97. 	cout << pos;
  98.  
  99.  
  100.  
  101.   return 0;
  102. }
Success #stdin #stdout 0.01s 7720KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/kY1IgJ
language:
C++ (gcc 8.3)
created:
1 day 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!