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
| import java.io.BufferedInputStream;
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(new BufferedInputStream(System.in));
int n = scanner.nextInt(), m = scanner.nextInt(), s = scanner.nextInt(), t = scanner.nextInt();
int[] dis = new int[n + 1];
int[][] edge = new int[n + 1][n + 1];
boolean[] vd = new boolean[n + 1];
Arrays.fill(dis, Integer.MAX_VALUE);
for (int i = 0; i < m; i++) {
int x = scanner.nextInt(), y = scanner.nextInt(), v = scanner.nextInt();
if (edge[x][y]==0){
edge[x][y] = v;
edge[y][x] = v;
}else if (edge[x][y] > v) {
edge[x][y] = v;
edge[y][x] = v;
}
}//初始化
int flag = s;
dis[flag] = 0;
vd[flag] = true;
while (flag != t) {
for (int i = 1; i < n + 1; i++) {
if (edge[flag][i] != 0 && !vd[i]) {
dis[i] = Math.min(edge[flag][i] + dis[flag], dis[i]);
}
}
int min = Integer.MAX_VALUE, minF = -1;
for (int i = 1; i < n + 1; i++) {
if (!vd[i]) {
if (min >= dis[i]) {
min = dis[i];
minF = i;
}
}
}
flag = minF;
vd[flag] = true;
}
System.out.println(dis[t]);
}
}
|
