fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4.  
  5. using namespace std;
  6. using namespace __gnu_pbds;
  7.  
  8. #define fi first
  9. #define se second
  10. #define mp make_pair
  11. #define pb push_back
  12. #define fbo find_by_order
  13. #define ook order_of_key
  14.  
  15. typedef long long ll;
  16. typedef pair<ll,ll> ii;
  17. typedef vector<int> vi;
  18. typedef long double ld; 
  19. typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
  20. typedef set<int>::iterator sit;
  21. typedef map<int,int>::iterator mit;
  22. typedef vector<int>::iterator vit;
  23.  
  24. ll cost[11][11];
  25. ll dist[100001][11];
  26. vector<pair<ii,int> > adj[100001];
  27. const ll INF = ll(1e18);
  28. int main()
  29. {
  30. 	ios_base::sync_with_stdio(0); cin.tie(0);
  31. 	int n, m, k, s; cin >> n >> m >> k >> s; s--;
  32. 	for(int i = 0; i < k; i++)
  33. 	{
  34. 		for(int j = 0; j < k; j++)
  35. 		{
  36. 			cin >> cost[i][j];
  37. 		}
  38. 	}
  39. 	for(int i = 0; i < m; i++)
  40. 	{
  41. 		int u, v, w, l; cin>>u>>v>>w>>l;
  42. 		u--; v--; l--;
  43. 		adj[u].pb(mp(mp(v,w),l)); adj[v].pb(mp(mp(u,w),l));
  44. 	}
  45. 	priority_queue<pair<ii,int>, vector<pair<ii,int> >, greater<pair<ii,int> > > pq;
  46. 	for(int i = 0; i < n; i++)
  47. 	{
  48. 		for(int j = 0; j < k; j++)
  49. 		{
  50. 			dist[i][j] = INF;
  51. 		}
  52. 	}
  53. 	for(int i = 0; i < k; i++) dist[s][i] = 0;
  54. 	pq.push(mp(mp(0,s),-1));
  55. 	while(!pq.empty())
  56. 	{	
  57. 		ll d = pq.top().fi.fi; int u = pq.top().fi.se; int c = pq.top().se; pq.pop();
  58. 		for(int i = 0; i < adj[u].size(); i++)
  59. 		{
  60. 			int v = adj[u][i].fi.fi; ll w = adj[u][i].fi.se; int e = adj[u][i].se;
  61. 			ll totd = d + w;
  62. 			if(c != -1) totd += cost[c][e];
  63. 			if(totd < dist[v][e])
  64. 			{
  65. 				dist[v][e] = totd;
  66. 				pq.push(mp(mp(totd,v),e));
  67. 			}
  68. 		}
  69. 	}
  70. 	for(int i = 0; i < n; i++)
  71. 	{
  72. 		ll mincost = INF;
  73. 		for(int j = 0; j < k; j++)
  74. 		{
  75. 			mincost = min(mincost, dist[i][j]);
  76. 		}
  77. 		if(mincost == INF) mincost = -1;
  78. 		cout<<mincost<<' ';
  79. 	}
  80. }
  81.  
Runtime error #stdin #stdout 0s 13232KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/9gLly5
language:
C++14 (gcc 8.3)
created:
7 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!