uva 10048(最短)
テーマの意味はn都市があって、m街があって、すべての街は騒音があります
起点から終点まで、少なくともどれだけの騒音に耐えなければならないかを聞いてみましょう(注意は和ではなく、通りかかった街の中で一番大きいものです.)
ACコード:
起点から終点まで、少なくともどれだけの騒音に耐えなければならないかを聞いてみましょう(注意は和ではなく、通りかかった街の中で一番大きいものです.)
ACコード:
#include
const int N = 105 ;
const int INF = 0x3f3f3f3f;
int g[N][N];
int c,s,q;
int main () {
int a,b,d;
int cas = 1;
int first = 1;
while(scanf("%d%d%d",&c,&s,&q) && c) {
if (first == 1) {
first++;
}
else {
printf("
");
}
for (int i = 1 ; i <= c ;i++) {
for (int j = 1 ; j <= c ;j++) {
g[i][j] = INF;
}
}
for (int i = 0 ; i < s ;i++) {
scanf("%d%d%d",&a,&b,&d);
g[a][b] = d;
g[b][a] = d;
}
for (int k = 1 ; k <= c ;k++) {
for (int i = 1 ; i <= c ;i++) {
for (int j = 1 ; j <= c ;j++) {
if(g[i][k] != INF && g[k][j] != INF) {
int m = g[i][k] > g[k][j] ? g[i][k] : g[k][j];
if(m < g[i][j])
g[i][j] = m;
}
}
}
}
printf("Case #%d
",cas++);
for (int i = 0 ; i < q ;i++) {
scanf("%d%d",&a,&b) ;
if(g[a][b] < INF)
printf("%d
",g[a][b]);
else
printf("no path
");
}
}
}