Heavy Transportation

• 这题是最短路题型的变形，该题不是求起点到终点的最短路，而是求路径中的最小边的最大值。

• 这题的求解思路是：将原来dijkstra中的松弛方程改一下，改成求最小边的最大值的松弛方程:d[j]=max(d[j],min(d[i],w[i][j]))。

  #include
  #include
  #include
  #include
  #include
  #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;imm)
  {
  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++;
        }
    }

}