fork download
copy 
  1. /*input
  2. 5 4 3 1
  3. 1 1 1
  4. 1 1 1
  5. 1 1 1
  6. 1 2 1 2 0
  7. 2 3 2 3 0
  8. 3 4 1 2 0
  9. 4 5 2 3 0
  10. */
  11. #include<bits/stdc++.h>
  12. using namespace std;
  13. const int N=5001;
  14. #define int long long
  15. #define pii pair<int, int>
  16. #define f first
  17. #define s second
  18. inline pii mp(int a, int b)
  19. {
  20. 	pii temp;temp.f=a;temp.s=b;return temp;
  21. }
  22. int graph[101][101][101], n, nd, m, K;
  23. vector< pii > adjlist[N];
  24. priority_queue<pii, vector<pii>, greater< pii > > pq;
  25. int dist[N];
  26. void fw()
  27. {
  28. 	for(int ind=0;ind<101;ind++)
  29. 	{
  30. 		for(int k=1;k<=nd;k++)
  31. 		{
  32. 			for(int i=1;i<=nd;i++)
  33. 			{
  34. 				for(int j=1;j<=nd;j++) graph[ind][i][j]=min(graph[ind][i][k] + graph[ind][k][j], graph[ind][i][j]);
  35. 			}
  36. 		}
  37. 	}
  38. }
  39. signed main()
  40. {
  41. 	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
  42. 	//freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
  43. 	cin>>n>>m>>nd>>K;
  44. 	for(int i=1;i<=nd;i++)
  45. 	{
  46. 		for(int j=1;j<=nd;j++)
  47. 		{
  48. 			cin>>graph[0][i][j];
  49. 			if(graph[0][i][j]==-1) graph[0][i][j]=1e17;;
  50. 		}
  51. 	}
  52.  
  53. 	for(int i=1;i<101;i++)
  54. 	{
  55. 		for(int j=1;j<=nd;j++)
  56. 		{
  57. 			for(int k=1;k<=nd;k++)
  58. 			{
  59. 				graph[i][j][k]=graph[i-1][j][k];
  60. 				if(j==i||k==i) graph[i][j][k]+=K;
  61. 			}
  62. 		}
  63. 	}
  64. 	fw();
  65. 	for(int i=1;i<=m;i++)
  66. 	{
  67. 		int a, b, c, u, v;
  68. 		cin>>u>>v>>a>>b>>c;
  69. 		int w=graph[c][a][b];//cout<<w<<endl;
  70. 		adjlist[u].push_back(mp(v, w));adjlist[v].push_back(mp(u, w));
  71. 	}
  72. 	for(int i=1;i<=n;i++) dist[i]=1e17;
  73. 	dist[1]=0;
  74. 	pq.push(mp(0, 1));
  75. 	while(!pq.empty())
  76. 	{
  77. 		pii cur=pq.top();pq.pop();
  78. 		if(cur.f>dist[cur.s]) continue;
  79. 		for(auto j:adjlist[cur.s])
  80. 		{
  81. 			if(dist[j.f]>dist[cur.s] + j.s)
  82. 			{
  83. 				dist[j.f]=dist[cur.s]+j.s;pq.push(mp(dist[j.f], j.f));
  84. 			}
  85. 		}
  86. 	}
  87. 	for(int i=2;i<=n;i++)
  88. 	{
  89. 		if(dist[i]==1e17) dist[i]=-1;
  90. 		cout<<dist[i]<<endl;
  91. 	}
  92. }
Success #stdin #stdout 0s 23440KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/HU3a1w
language:
C++14 (gcc 8.3)
created:
6 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!