uva 10099 The Tourist Guide(单源最短路/spfa/dijkstra)

题目：

        链接：点击打开链接

题意：

思路：

代码：

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;

int map[101][101];

void floyd(int n)
{
    for(int k=1; k<=n; k++)
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
                map[i][j] = max(map[i][j],min(map[i][k], map[k][j]));
}

int main()
{
    //freopen("input.txt","r",stdin);
    int n, r;
    int x,y,p;
    int st,ed,w;
    int kase = 1;
    while(scanf("%d%d", &n, &r) != EOF && (n+r))
    {
        memset(map, 0, sizeof(map));
        for(int i=0; i<r; i++)
        {
            scanf("%d%d%d", &x, &y, &p);
            map[y][x] = map[x][y] = p;
        }
        scanf("%d%d%d", &st, &ed, &w);
        floyd(n);
        printf("Scenario #%d\n", kase++);
        int result = w / (map[st][ed]-1);
        if(w % (map[st][ed]-1))
            result++;
        printf("Minimum Number of Trips = %d\n\n",result);
    }
    return 0;
}

收获：

----->

------------------------------------------------------------------

战斗，从不退缩；奋斗，永不停歇~~~~~~~~~~~~~~

uva 10099 The Tourist Guide(单源最短路/spfa/dijkstra),布布扣,bubuko.com

uva 10099 The Tourist Guide(单源最短路/spfa/dijkstra)

原文：http://blog.csdn.net/u013147615/article/details/36055873