Heavy Transportation

POJ-1797

这题是最短路题型的变形，该题不是求起点到终点的最短路，而是求路径中的最小边的最大值。
这题的求解思路是：将原来dijkstra中的松弛方程改一下，改成求最小边的最大值的松弛方程:d[j]=max(d[j],min(d[i],w[i][j]))。

#include <algorithm>

#include <iostream>

#include <cmath>

#include <cstdio>

#include <cstring>

#define INF 0x3f3f3f3f

#define MOD 1e9+7

using namespace std;

int e[1005][1005];

int dis[1005];

bool vis[1005];

int main()

{

	int T,n,m,ca=0;

	cin>>T;

	while(T--)

	{

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

		memset(e,0,sizeof(e));

		int a,b,w;

		for(int i=0;i<m;i++)

		{

            scanf("%d%d%d",&a,&b,&w);

            e[a][b]=e[b][a]=w;

		}

		dis[1]=INF;

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

            dis[i]=e[1][i];

		memset(vis,false,sizeof(vis));

        for(int k=0;k<n;k++)

        {

            int mi,mm=-INF;

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

            {

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

                {

                    mm=dis[i];

                    mi=i;

                }

            }

            vis[mi]=true;

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

            {

                if(!vis[i])

                    dis[i]=max(dis[i],min(dis[mi],e[mi][i]));

            }

        }

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

	}

	return 0;

}

java:

package POJ;

import java.util.*;

public class POJ_1797 {

	private static int n,m;//n:1-1000

	static int t;//case

	static int [][]w;

	static int []dis;

	static boolean []flag;

	static final int INF=0X3F3F3F3F;

	static int s,e;

	static  int dijkstra() {

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

			int index=-1,mins=INF;

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

				if(!flag[j]&&dis[j]>mins) {

					mins=dis[index=j];

				}

			}

			if(index==-1)

				break;

			flag[index]=true;

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

				if(!flag[j])

					dis[j]=Math.max(dis[j],Math.min(dis[index],w[index][j]));

			}

		}

		return dis[e];

	}

	public static void main(String[] args) {

		// TODO Auto-generated method stub

		Scanner cin=new Scanner(System.in);

		t=cin.nextInt();

		int cnt=1;

		while(t>0) {

			n=cin.nextInt();

			m=cin.nextInt();

			w=new int[n][n];

			dis=new int[n];

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

				int from,to;

				from=cin.nextInt();

				to=cin.nextInt();

				w[from-1][to-1]=w[to-1][from-1]=cin.nextInt();

			}

			s=0;e=n-1;

			dis[s]=INF;

			flag=new boolean[n];

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

				dis[i]=w[0][i];

			}

			flag[s]=true;

			System.out.println("Scenario #"+cnt+":");

			System.out.println(dijkstra());

			t--;

			cnt++;

		}

	}

}

巴特西

POJ-1797(最短路变形-dijkstra)

Heavy Transportation

POJ-1797

最新文章

热门文章