![](//static.nowcoder.com/images/logo_87_87.png)
我也给两个全A参考。
第一题:
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
long[][] cityAndDis = new long[6][6];
for (int i = 0; i < 6; i++) {
for (int j = 0; j < 6; j++) {
int x = in.nextInt();
if (x == -1)
cityAndDis[i][j] = Integer.MAX_VALUE;
else
cityAndDis[i][j] = x;
}
}
int start = 0;
long[] ans = Dijkstra(cityAndDis, start);
for (int i = 1; i < 6; i++) {
System.out.println(ans[i]);
}
}
private static long[] Dijkstra(long[][] cityAndDis, int start) {
long[] city = new long[cityAndDis.length];
long[] ans = new long[cityAndDis.length];
city[start] = 1;
ans[start] = 0;
for (int i = 1; i < cityAndDis.length; i++) {
long min = Long.MAX_VALUE;
int k = 0;
for (int j = 0; j < cityAndDis.length; j++) {
if (city[j] == 0 && cityAndDis[start][j] < min) {
k = j;
min = cityAndDis[start][j];
}
}
city[k] = 1;
ans[k] = min;
for (int j = 0; j < cityAndDis.length; j++) {
if (city[j] == 0 && cityAndDis[k][j] + cityAndDis[start][k] < cityAndDis[start][j]) {
cityAndDis[start][j] = cityAndDis[k][j] + cityAndDis[start][k];
}
}
}
return ans;
}