AcWing 849. Dijkstra求最短路 I-java
原题链接
简单
作者:
Astarion
,
2021-02-12 17:01:25
,
所有人可见
,
阅读 174
import java.io.*;
import java.util.*;
class Main {
//注意!此处不能设为最大整数,因为判断过程有+操作,会将最大整数加到负值
static final int INF = Integer.MAX_VALUE/2;
static int n,m;
//稠密图,邻接矩阵存储
static int[][] g = new int[520][520];
//从起点到其他点距离
static int[] dist = new int[520];
static boolean[] flag = new boolean[520];
static {
for (int i = 1; i<519; i++) Arrays.fill(g[i],INF);
Arrays.fill(dist,INF);
for (int i = 1; i<519; i++) g[i][i] = 0;
}
static void insert(int a, int b, int v) {
g[a][b] = Math.min(g[a][b], v);
}
static void generateDistance(int start) {
dist[start] = 0;
for (int i=1; i<=n; i++) {
int minV = INF;
int next = 0;
//找到当前距离最近的点next
for (int j = 1; j<=n; j++) {
if (dist[j]<minV && !flag[j]) {
minV = dist[j];
next = j;
}
}
//没找到,返回
if (next == 0) return;
//找到n,返回
if (next == n) return;
flag[next] = true;
for (int j = 1; j<=n; j++) {
if (!flag[j] && dist[j]>dist[next]+g[next][j]) dist[j] = dist[next] + g[next][j];
}
}
}
public static void main(String[] args) throws IOException {
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader in = new BufferedReader(isr);
String[] strs = in.readLine().split(" ");
n = Integer.parseInt(strs[0]);
m = Integer.parseInt(strs[1]);
for (int i=0; i<m; i++) {
strs = in.readLine().split(" ");
int a = Integer.parseInt(strs[0]);
int b = Integer.parseInt(strs[1]);
int v = Integer.parseInt(strs[2]);
insert(a,b,v);
}
in.close();
isr.close();
generateDistance(1);
if (dist[n] == INF) dist[n] = -1;
System.out.println(dist[n]);
}
}