Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

附java的AC代码

Posted by a914456697 at 2018-08-24 17:14:17 on Problem 2387
```import java.util.Scanner;

public class POJ_2387 {
private static final int INF = 400000;
private static int T, N;
private static int[][] map;
private static int[] dis;
private static boolean[] vis;

public static void main(String[] args) {
Scanner in = new Scanner(System.in);
T = in.nextInt();
N = in.nextInt();
dis = new int[N + 1];
vis = new boolean[N + 1];
map = new int[N + 1][N + 1];
for (int i = 1; i <= N; i++) {
dis[i] = INF;
for (int j = 1; j <= N; j++) {
map[i][j] = map[j][i] = INF;
}
}
while (T-- > 0) {
int s = in.nextInt();
int e = in.nextInt();
int w = in.nextInt();
//如果有重边，选择最小的
if (map[s][e] > w)
map[s][e] = map[e][s] = w;
}
dijkstra(1);
System.out.println(dis[N]);
in.close();
}

private static void dijkstra(int u) {
for (int i = 1; i <= N; i++) {
dis[i] = map[u][i];
}
dis[u] = 0;
vis[u] = true;
for (int t = 0; t < N; t++) {
int min = INF;
int k = 0;
for (int i = 1; i <= N; i++) {
if (!vis[i] && dis[i] < min) {
min = dis[i];
k = i;
}
}
vis[k] = true;
for (int i = 1; i <= N; i++) {
if (!vis[i] && dis[i] > dis[k] + map[k][i])
dis[i] = dis[k] + map[k][i];
}
}
}

}```

Followed by: