fork(1) download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <climits>
  4. using namespace std;
  5.  
  6. int A[510][510][24];
  7. int dist[510][24];
  8. bool sptSet[510];
  9.  
  10. int minDistance(int i, int V)
  11. {
  12.    // Initialize min value
  13.    int _min = INT_MAX, min_index;
  14.  
  15.    for (int v = 0; v < V; v++)
  16.      if (sptSet[v] == false && dist[v][i] <= _min)
  17.          _min = dist[v][i], min_index = v;
  18.    return min_index;
  19. }
  20.  
  21. void dijkstra(int x, int V, int src)
  22. {
  23.      // Distance of source vertex from itself is always 0
  24.      dist[src][x] = 0;
  25.  
  26.      // Find shortest path for all vertices
  27.      for (int count = 0; count < V-1; count++)
  28.      {
  29.        // Pick the minimum distance vertex from the set of vertices not
  30.        // yet processed. u is always equal to src in first iteration.
  31.        int u = minDistance(x, V);
  32.  
  33.        // Mark the picked vertex as processed
  34.        sptSet[u] = true;
  35.  
  36.        // Update dist value of the adjacent vertices of the picked vertex.
  37.        for (int v = 0; v < V; v++)
  38.  
  39.          // Update dist[v] only if is not in sptSet, there is an edge from
  40.          // u to v, and total weight of path from src to  v through u is
  41.          // smaller than current value of dist[v]
  42.          if (!sptSet[v] && A[u][v][x] && dist[u][x] != INT_MAX
  43.                                        && dist[u][x]+A[u][v][x] < dist[v][x])
  44.             dist[v][x] = dist[u][x] + A[u][v][x];
  45.      }
  46. }
  47.  
  48. int main() {
  49. 	// your code goes here
  50. 	int N, K, T, M, x, y, i, j, D, S, k, t=1;
  51. 	cin>>T;
  52. 	while(T--)
  53. 	{
  54. 		cin>>N>>M>>K;
  55. 		for(i=0; i<N; ++i)
  56. 		{
  57. 			for(j=0; j<24; ++j)
  58. 				dist[i][j]=INT_MAX;
  59. 		}
  60. 		for(i=0; i<N; ++i)
  61. 			for(j=0; j<N; ++j)
  62. 				for(k=0; k<24; ++k)
  63. 					A[i][j][k]=0;
  64. 		for(i=0; i<M; ++i)
  65. 		{
  66. 			cin>>x>>y;
  67. 			for(j=0; j<24; ++j)
  68. 			{
  69. 				cin>>A[x-1][y-1][j];
  70. 				A[y-1][x-1][j]=A[x-1][y-1][j];
  71. 			}
  72. 		}
  73. 		for(i=0; i<24; ++i)
  74. 		{
  75. 			for(j=0; j<N; ++j)
  76. 				sptSet[j]=false;
  77. 			dijkstra(i, N, 0);
  78. 		}
  79. 		cout<<"Case #"<<t<<": ";
  80. 		while(K--)
  81. 		{
  82. 			cin>>D>>S;
  83. 			if(dist[D-1][S]==INT_MAX)
  84. 				cout<<"-1 ";
  85. 			else
  86. 				cout<<dist[D-1][S]<<" ";
  87. 		}
  88. 		cout<<endl;
  89. 		t++;
  90. 	}
  91. 	return 0;
  92. }
Success #stdin #stdout 0s 27896KB
comments (?)
stdin
copy 
1
15 40 50
1 2
10 24 30 29 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11
1 5
5 13 21 21 21 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6
1 10
5 20 20 19 21 23 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6
1 12
9 20 27 28 28 27 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10
1 14
9 8 25 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10
2 3
2 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3
2 5
9 16 15 24 24 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10
2 6
5 18 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6
2 7
8 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9
2 8
8 28 27 27 26 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9
2 11
7 28 27 26 25 24 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8
2 13
9 15 20 29 28 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10
3 4
6 27 27 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7
3 11
9 14 23 27 28 27 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10
3 12
1 22 22 21 20 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2
3 14
3 20 21 20 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4
4 7
9 21 30 29 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10
4 8
10 16 26 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11
4 12
8 30 29 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9
4 13
7 20 23 26 25 24 24 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8
5 6
7 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8
5 15
3 21 23 22 21 20 20 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4
6 8
6 14 26 25 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7
6 9
4 9 22 22 22 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5
6 11
4 15 21 24 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5
6 12
8 21 29 28 27 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9
7 10
9 23 26 27 26 27 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10
7 11
8 26 27 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9
7 12
10 20 31 30 29 28 27 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11
7 14
3 19 18 21 20 21 20 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4
8 9
2 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3
8 10
4 8 19 18 17 20 19 20 19 18 17 16 16 15 14 13 12 11 10 9 8 7 6 5
8 12
3 11 20 21 22 21 20 19 18 17 16 15 15 14 13 12 11 10 9 8 7 6 5 4
8 14
9 10 27 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10
9 12
5 26 25 25 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6
9 15
3 2 15 18 17 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4
10 11
5 22 21 23 24 23 22 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6
11 15
7 11 13 24 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8
12 13
3 14 24 23 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4
14 15
1 14 22 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2
2 2
2 7
2 18
2 20
2 22
4 9
4 20
4 21
4 23
5 7
5 8
5 15
5 16
5 19
5 21
6 3
6 4
6 5
6 20
8 3
8 8
8 13
8 14
8 23
9 1
9 5
9 6
9 7
10 15
10 22
11 7
11 15
11 18
12 0
12 7
12 11
12 13
12 15
12 21
13 2
13 5
13 17
13 21
14 11
14 14
15 3
15 10
15 13
15 16
15 21
stdout
copy 
Case #1: 30 27 16 14 12 47 25 23 19 22 21 14 13 10 8 49 48 50 20 37 40 31 29 11 24 51 50 48 14 7 44 28 22 9 26 22 20 18 12 50 49 26 18 22 19 43 36 30 24 14
https://ideone.com/cle94b
language:
C++14 (gcc 8.3)
created:
9 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!