-
Notifications
You must be signed in to change notification settings - Fork 2
/
10099.cpp
55 lines (47 loc) · 882 Bytes
/
10099.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
#include<stdio.h>
#define MAX(A, B) (A>B?A:B)
#define MIN(A, B) (A>B?B:A)
#define MAXN 102
#define INF 21474836
int A[MAXN][MAXN];
int N, M;
void Ini() {
int i, j;
for(i = 1; i<=N; i++)
for(j = 1; j <= N; j++)
A[i][j] = 0;
}
void Floyd() {
int i, j, k;
for(k = 1; k <= N; k ++) {
for(i = 1; i < N; i++) {
for(j = 1+i; j <= N; j ++) {
A[i][j] = A[j][i] = MAX(A[i][j],MIN(A[i][k],A[k][j]));
}
}
}
}
void Cal(int a, int b, int c) {
int p;
p = c/(A[a][b]-1);
if(c>p*(A[a][b]-1)) p++;
printf("Minimum Number of Trips = %d\n",p);
}
int main() {
int i, a, b, c;
int kase = 1;
while(scanf("%d%d",&N, &M) == 2) {
if(!N && !M) break;
Ini();
for(i = 0; i<M; i++) {
scanf("%d%d%d",&a,&b,&c);
A[a][b] = A[b][a] = c;
}
Floyd();
scanf("%d%d%d",&a,&b,&c);
printf("Scenario #%d\n",kase++);
Cal(a,b,c);
putchar('\n');
}
return 0;
}