学步园

链接地址：http://poj.org/problem?id=3615

题意简单。给你一个有向图，然后给你一些起点s和终点e，问s到e的所有路径中经过的边的边权值最大的最小的是多少。若s到e不可达则输出-1。


用floyd算法可以解决掉。不过要修改一下。

Accepted        528K        532MS        C        险过~

code:

#include <stdio.h>
#include <string.h>
#define MAXN 305
#define INF 0x7f7f7f7f

int d[MAXN][MAXN];

void floyd(int n) {
    int i, j, k, tmp;
    for(k=1; k<=n; k++)
        for(i=1; i<=n; i++)
            for(j=1; j<=n; j++)
                if(d[i][k]<INF&&d[k][j]<INF) {
                    if(d[i][k]>d[k][j])
                        tmp = d[i][k];
                    else
                        tmp = d[k][j];

                    if(d[i][j]==INF) {
                        d[i][j] = tmp; // d[i][j] = max(d[i][k],d[k][j]);
                    } else if(tmp<d[i][j])
                        d[i][j] = tmp; // d[i][j] = min( d[i][j], max(d[i][k],d[k][j]) ）；
                }
}
int main() {
    int N, M, T, i, v, u, len, s, e;
    while(~scanf("%d%d%d",&N,&M,&T)) {
        memset(d,INF,sizeof(d));
        for(i=0; i<M; i++) {
            scanf("%d%d%d",&v,&u,&len);
            d[v][u] =len;
        }
        floyd(N);
        for(i=0; i<T; i++) {
            scanf("%d%d",&s,&e);
            if(d[s][e]==INF)
                printf("-1\n");
            else printf("%d\n",d[s][e]);
        }
    }
    return 0;
}