学步园

这道题是求来回用的时间最多的时间。而其中，去参加party和回去的时间都要是最短的，所以可以用dijkstra算法解。

                                                                         Source Code

import java.util.Arrays;<br /> import java.util.Scanner; </p> <p>public class Main { </p> <p> public static void main(String[] args) { </p> <p> Scanner sc = new Scanner(System.in);<br /> int n = sc.nextInt();<br /> int m = sc.nextInt();<br /> int x = sc.nextInt();<br /> int[][] map1 = new int[n + 1][n + 1];<br /> int[][] map2 = new int[n + 1][n + 1];</p> <p> boolean[] visted = new boolean[n + 1];<br /> int[] dist1 = new int[n + 1];<br /> int[] dist2 = new int[n + 1];</p> <p> for (int i = 0; i < m; i++) {<br /> int a = sc.nextInt();<br /> int b = sc.nextInt();<br /> int t = sc.nextInt();<br /> map1[a][b] = t;<br /> map2[b][a] = t;<br /> } </p> <p> dijkstra(visted, dist1, map1, x); </p> <p> dijkstra(visted, dist2, map2, x); </p> <p> int max = Integer.MIN_VALUE; </p> <p> for (int i = 1; i <= n; i++) {<br /> if (dist1[i] + dist2[i] > max) {<br /> max = dist1[i] + dist2[i];<br /> }<br /> } </p> <p> System.out.println(max);<br /> } </p> <p> public static void dijkstra(boolean[] visted, int[] dist, int[][] map, int x) {<br /> Arrays.fill(visted, false);<br /> Arrays.fill(dist, Integer.MAX_VALUE); </p> <p> visted[x] = true; </p> <p> // 初始化dist数组<br /> for (int i = 1; i < dist.length; i++) {<br /> if (!visted[i] && map[x][i] != 0) {<br /> dist[i] = map[x][i];<br /> }<br /> } </p> <p> while (true) { </p> <p> int temp = 0;<br /> int min = Integer.MAX_VALUE;</p> <p> //找出花费最少时间的路径<br /> for (int i = 1; i < dist.length; i++) {<br /> if (dist[i] < min && !visted[i]) {<br /> min = dist[i];<br /> temp = i;<br /> }<br /> }<br /> // x = temp;<br /> if (temp == 0)<br /> break;<br /> visted[temp] = true;</p> <p> //更新目前x到其他点的最短路径<br /> for (int i = 1; i < dist.length; i++) { </p> <p> if (!visted[i] && map[temp][i] != 0<br /> && dist[i] > dist[temp] + map[temp][i]) {<br /> dist[i] = dist[temp] + map[temp][i];<br /> }<br /> }<br /> }<br /> }<br /> }<br />