POJ.1797 Heavy Transportation (Dijkstra变形)

题意分析

给出n个点，m条边的城市网络，其中 x y d 代表由x到y(或由y到x)的公路所能承受的最大重量为d，求从1到n的所有通路中，所能经过的的最大重量的车为多少。

代码总览

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <queue>

#include <stack>

#include <vector>

#include <cmath>

#define nmax 1005

#define inf 1e8+7

using namespace std;

int t,n,m;

int mp[nmax][nmax];

int shortpath[nmax];

bool visit[nmax];

void dij(int s)

{

    int cur = s;

    memset(visit,0,sizeof(visit));

    for(int i = 1;i<=n;++i){shortpath[i] = mp[cur][i];}

    shortpath[cur] = 0;

    visit[cur] = true;

    for(int i = 1;i<=n-1 ;++i){

        int minL = 0;

        for(int j = 1;j<=n;++j){

            if(!visit[j] && shortpath[j] != 0 && shortpath[j] >minL){

                minL = shortpath[j];

                cur = j;

            }

        }

        visit[cur] = true;

        for(int j = 1;j<=n;++j){

            if(!visit[j]){

                shortpath[j] = max(min(mp[cur][j],shortpath[cur]),shortpath[j]);

            }

        }

    }

}

void init()

{

    scanf("%d %d",&n,&m);

    for(int i = 1;i<=n;++i)

        for(int j = 1;j<=n;++j)

            mp[i][j] = 0;

    for(int i = 1;i<=m;++i){

        int sta,end,dis;

        scanf("%d %d %d",&sta,&end,&dis);

        mp[sta][end] = mp[end][sta] = dis;

    }

}

int main()

{

    //freopen("in.txt","r",stdin);

    int kase  = 1;

    scanf("%d",&t);

    for(int i = 1;i<=t;++i){

        init();

        dij(1);

        printf("Scenario #%d:\n",kase++);

        printf("%d\n\n",shortpath[n]);

    }

    return 0;

}