poj 1797 Heavy Transportation

 

Memory:4156K  Time:313MS

 

解题思路

题意：

    有n个街口，在m条街上运送东西，从第一个街口到第n个，求的是可以最多运送多少货物，就是去的路上能承受重量最大的那条路的权。也就是求最大路径的最小权值。

 

思路：

       是dijkstra的变形，从1到n求最大路径。求的时候用path记录下所经过的路，走完后再找出整条路中最小的权值。 要注意的是：更新dis的时候是更换下一步的权值最小的路，而不是整条最短的路。

源程序

 

#include <stdio.h>
#include <conio.h>
#include <string.h>
#define N 1010
int g[N][N];

void dijkstra(int n)
{
    int i,j;
    int min, minid, minest, dis[N], mark[N], path[N];

    for(i=1; i<=n; i++)
    {
        dis[i] = g[1][i];
        mark[i] = 0;
        if(dis[i] > 0)
            path[i] = 1;
        else path[i] = 0;
    }
    mark[1] = 1;
    path[1] = 0;
    for(i=1; i<n; i++)
    {
        min = 0;
        minid = 0;
        for(j=1; j<=n; j++)
            if(!mark[j] && dis[j] > min)
            {
                min = dis[j];
                minid = j;
            }
        if(!minid || minid == n)
            break;
        mark[minid] = 1;
        
        for(j=1; j<=n; j++)
            if(!mark[j] && g[minid][j] > dis[j])   //这里这里，wa了好多
            {
                dis[j] = g[minid][j];
                path[j] = minid;
            }
    }
    if(!minid)
        printf("0\n");
    else
    {
        minest = 0xfffffff;
        while(path[minid])   //找出最小权
        {
            if(g[path[minid]][minid] < minest )
                minest = g[path[minid]][minid];
            minid = path[minid];
            
        }
        printf("%d\n\n", minest);
    }
}

int main()
{
    int t, n, m, x, y, k=0, w;

    freopen("in.txt", "r", stdin);
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d%d", &n, &m);
        memset(g, 0, sizeof(g));
        while(m--)
        {
            scanf("%d%d%d", &x, &y, &w);
            g[y][x] = g[x][y] = w;
        }
        k++;
        printf("Scenario #%d:\n", k);
        dijkstra(n);
    }
    getch();
    return 0;
}