题目链接：用户登录
问题描述
A 国有 NN 个城市, 编号为 1…N 。小明是编号为 1 的城市中一家公司的员 工, 今天突然接到了上级通知需要去编号为 N 的城市出差。
由于疫情原因, 很多直达的交通方式暂时关闭, 小明无法乘坐飞机直接从 城市 1 到达城市 NN, 需要通过其他城市进行陆路交通中转。小明通过交通信息 网, 查询到了 MM 条城市之间仍然还开通的路线信息以及每一条路线需要花费的 时间。
同样由于疫情原因, 小明到达一个城市后需要隔离观察一段时间才能离开 该城市前往其他城市。通过网络, 小明也查询到了各个城市的隔离信息。(由于 小明之前在城市 1 , 因此可以直接离开城市 1 , 不需要隔离）
由于上级要求, 小明希望能够尽快赶到城市 N, 因此他求助于你, 希望你 能帮他规划一条路线, 能够在最短时间内到达城市 N 。
输入格式
第 1 行: 两个正整数 N, M, 表示 A 国的城市数量, M 表示末关闭的路 线数量
第 2 行: N 个正整数, 第 ii个整数 C_Ci 表示到达编号为i 的城市后需要隔离 的时间
第 3 …M+2 行: 每行 3 个正整数, u, v, c 表示有一条城市 uu 到城市 vv的 双向路线仍然开通着, 通过该路线的时间为 c
输出格式
第 1 行: 1 个正整数, 表示小明从城市 1 出发到达城市 NN 的最短时间（到 达城市 N, 不需要计算城市 N 的隔离时间）
样例输入
4 4 5 7 3 4 1 2 4 1 3 5 2 4 3 3 4 5
样例输出
13
样例说明：
编辑
代码：
import java.util.Arrays; import java.util.Scanner; public class 出差 { public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); int a[] = new int [n+1]; int s[] = new int[n+1]; for (int i = 1; i <= n; i++) { s[i] = sc.nextInt(); } int dp[][] = new int[n+1][n+1]; int f[] = new int[n+1]; for (int i = 0; i < dp.length; i++) { for (int j = 0; j < dp[i].length; j++) { dp[i][j] = 9999; } } for (int i = 0; i < m; i++) { int w = sc.nextInt(); int v = sc.nextInt(); int c = sc.nextInt(); dp[w][v] = c + s[v]; dp[v][w] = c+ s[w]; } for (int i = 1; i <=n; i++) { a[i] = dp[1][i]; } int index=0; a[1] = 0; f[1] = 1; for (int i = 1; i <= n; i++) { int min = 9999; for (int j = 1; j <=n; j++) { if(f[j]==0&&a[j]<min) { min = a[j]; index = j; } } f[index] = 1; for (int k = 1; k <=n; k++) { if(f[k]==0&&a[index]+dp[index][k]<a[k]) a[k] = a[index]+dp[index][k]; } } System.out.println(a[n]-s[n]); } }
