dij求最长路

3.dijkstra（适用于无负权边）

基本：
1.时间复杂度：

• 直接扫描所有未收录顶点：O(|V|)
  T=O(|v|² +|E|)——对稠密图效果好
• 将dist存在最小堆里：O（log|V|)
  T=O(|E|log|V|)——对稀疏图效果好

2.用于求多点到固定点的最短路
扩展：
1.变形的dijkstra,寻找从1到N的所有[通路中的那条最小边]的值中的最大值.
与原板子区别:
1.改变cost[][]的初始值为0,而非INF.因为更新d[]时要选最大的啦!
2.所有d[i]初始值为cost[1][i],而非将d[i]初始化为INF的d[1]为0
3.寻找要放入vis的点u时,找值最大的,而非最小的
4.更新d[]时,d[v]=Math.max(d[v], Math.min(w[u][v], d[u]));

以下为AC代码,注意注释

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;

public class Main{
	public static StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
	public static int N,ans,maxn=1010,w[][]=new int[maxn][maxn],d[]=new int[maxn];
	public static boolean vis[]=new boolean[maxn];
	public static int dij() {
		for(int i=1;i<=N;i++) {
			d[i]=w[1][i];
		}
		for(int i=1;i<=N;i++) {
			vis[i]=false;
		}
		vis[1]=true;
		while(true) {
			//System.out.println("?");
			int cur=0,u=0;//cur:当前从1到达所有点的所有通路中的最小值的最大值
			for(int i=1;i<=N;i++) {
			//当d[i]值比当前所有其他点的d值都大时,1到i的所有路径中的最小值的最大值也就确定了
			//因为每次更新d[i]一定要经过其他的点,但是到达这些点的路径中最小值的最大值都比d[i]小了,再检验也不会更新.
				if(!vis[i]&&d[i]>cur) {
					cur=d[i];
					u=i;
				}
			}

			if(u==0) {
				break;
			}
			vis[u]=true;
			for(int v=1;v<=N;v++) {
				if(!vis[v]) {
					d[v]=Math.max(d[v], Math.min(w[u][v], cur));
				}
			}
		}
		return d[N];
	}
	
	public static int nextInt() throws IOException {
		in.nextToken();
		return (int)in.nval;
	}
	
	public static void main(String args[]) throws Exception{
		int T;
		T=nextInt();
		int f=T;
		while(T-->0) {
			N=nextInt();
			int M=nextInt();
			int u,v,c;
			for(int i=1;i<=N;i++) {
				for(int j=1;j<=N;j++) {
					w[i][j]=0;
				}
			}
			for(int i=0;i<M;i++) {
				u=nextInt();
				v=nextInt();
				c=nextInt();
				w[u][v]=c;
				w[v][u]=c;
			}
			System.out.print("Scenario #"+(f-T)+":"+"\n");
			System.out.print(dij()+"\n");
			System.out.println();
		}

	
	}

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77