printf("Scenario #%d\n", cas++);
printf("Minimum Number of Trips = %d\n\n",t);
}
return 0;
}
2. Floyd
[cpp]
#include
#include
const int N = 105;
const int INF = 1000000000;
using namespace std;
int n,m,beg,end,limit,d[N][N];
inline void read_graph(){
for(int i=1; i<=n; ++i){
d[i][i] = 0;
for(int j=i+1; j<=n; ++j)
d[i][j]=d[j][i]=INF;
}
int a,b,c;
for(int i=0; i
d[a][b]=d[b][a]=c;
}
inline void Floyd(){
for(int k=1; k<=n; ++k)
for(int i=1; i<=n; ++i){
for(int j=1; j<=n; ++j){
int tmp = min(d[i][k], d[k][j]);
if(d[i][j]==INF) d[i][j] = tmp;
else d[i][j] = max(d[i][j],tmp);
}
}
}
int main(){
int a,b,c,cas=1;
while(~scanf("%d%d",&n,&m)&&n+m){
read_graph();
scanf("%d%d%d",&beg,&end,&limit);
Floyd();
int ans = d[beg][end];
int t=(limit%(ans-1)==0) (limit/(ans-1)):(limit/(ans-1)+1);
printf("Scenario #%d\n", cas++);
printf("Minimum Number of Trips = %d\n\n",t);
}
return 0;
}