-
Notifications
You must be signed in to change notification settings - Fork 1
/
UVa 341.cpp
85 lines (74 loc) · 1.48 KB
/
UVa 341.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <bits/stdc++.h>
#define mem(x,y) memset(x,y,sizeof(x));
using namespace std;
#define READ(f) freopen(f, "r", stdin)
#define WRITE(f) freopen(f, "w", stdout)
#define rep(i,n) for(int i = 1 ; i <= (n) ; i++)
#define iter(i,a,b) for(int i = (a) ; i < (b) ; i++)
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<int,pii> iii;
typedef vector <pii> vii;
#define INF 1000000000
#define MAXX 15
int V, E;
int adj_m[MAXX][MAXX], par[MAXX][MAXX];
void init()
{
rep(i, MAXX)
{
rep(j, MAXX)
{
adj_m[i][j] = INF;
par[i][j] = i;
}
}
}
void floyd_warshall()
{
rep(k, V)
{
rep(i, V)
{
rep(j, V)
{
if(adj_m[i][j] > (adj_m[i][k] + adj_m[k][j]) )
{
adj_m[i][j] = (adj_m[i][k] + adj_m[k][j]);
par[i][j] = par[k][j];
}
}
}
}
}
void printPath(int i, int j)
{
if(i != j)
printPath(i, par[i][j]);
printf(" %d", j);
}
int main()
{
READ("UVa 341.txt");
int tc, case_no = 0, v, w, n, src, dest;
while(true){
init();
cin>>V;
if(V == 0)
break;
for(int u = 1; u <= V; u++){
cin>>n;
for(int j = 0; j < n; j++){
cin>>v>>w;
adj_m[u][v] = w;
}
}
cin>>src>>dest;
floyd_warshall();
printf("Case %d: Path =", ++case_no);
printPath(src, dest);
printf("; %d second delay", adj_m[src][dest]);
printf("\n");
}
return 0;
}