Berlin Programming Contest 2004 Heavy Transportation /// dijkstra oj22604

题目大意：

输入t；t为样例数

每个样例输入n，m；n 为顶点个数 m 为路径数

接下来m行每行输入 u v w ；从 u 点到 v 点的路承重为 w

输出车子若想通过 1~n的最短路车重需限制在多少之内

Sample Input

1
3 3
1 2 3
1 3 4
2 3 5

Sample Output

Scenario #1:
4

邻接阵dijkstra

重点在此式 dis[i]=max(min(dis[ind],G[ind][i]),dis[i])

即更新 dis[] 时存入的应该是max（min（本条之前路径的承重限制，当前路段的承重限制），其他路径经过该点的承重限制）

经过同条路径各个路段的承重限制应选较小的

经过同一个点各条路径的承重限制应选较大的

#include<bits/stdc++.h>

#define INF 0x3f3f3f3f

using namespace std;

int n,m;

int G[][];

int vis[],dis[];

void dijk()

{

    while()

    {

        int maxi=-,ind;

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

            if(!vis[i] && dis[i]>maxi)

                maxi=dis[i], ind=i;

        if(maxi==-) break;

        vis[ind]=;

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

            if(!vis[i])

                dis[i]=max(min(dis[ind],G[ind][i]),dis[i]);

    }

}

int main()

{

    int  t; scanf("%d",&t);

    for(int j=;j<=t;j++)

    {

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

        memset(vis,,sizeof(vis));

        memset(G,,sizeof(G));

        while(m--)

        {

            int u,v,w;

            scanf("%d%d%d",&u,&v,&w);

            G[u][v]=G[v][u]=w;

        }

        vis[]=;

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

            if(!vis[i]) dis[i]=G[][i];

        dijk();

        printf("Scenario #%d:\n%d\n\n",j,dis[n]);

    }

    return ;

}

巴特西

Berlin Programming Contest 2004 Heavy Transportation /// dijkstra oj22604

最新文章

热门文章