题目
小赛要去位于 A 市的小码家。小赛来到 A 市的车站,买了一张 A 市的地图,他发现这里的地形非常的复杂。A 市的街道一共有 N 个路口,M 条道路,每条道路连接着两个路口,并且有各自的长度。目前,小赛所在的车站位于编号为 1 的路口,而小码家所在的路口编号为 N,小赛准备打出租车去,当然,路程越小,付的钱就越少。问题摆在眼前:请帮助小赛寻找一条最短路径,使得他可以花最少的钱到达小码家。
代码
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.StreamTokenizer; import java.util.Arrays; public class Main { static StreamTokenizer streamTokenizer = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); public static void main(String[] args) throws IOException { int n = nextInt(); int m = nextInt(); int[][] adj = new int[n + 1][n + 1]; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { adj[i][j] = Integer.MAX_VALUE; } } for (int i = 1; i <= n; i++) { adj[i][i] = 0; } for (int i = 0; i < m; i++) { int p1 = nextInt(); int p2 = nextInt(); int l = nextInt(); adj[p1][p2] = adj[p2][p1] = l; } int[] dist = new int[n + 1]; Arrays.fill(dist, Integer.MAX_VALUE); dist[1] = 0; boolean[] visited = new boolean[n + 1]; Arrays.fill(visited, false); for (int i = 1; i <= n; i++) { int cur = getMinIndex(dist, visited); visited[cur] = true; // 标记访问过结点 for (int j = 1; j <= n; j++) { if (!visited[j] && adj[cur][j] != Integer.MAX_VALUE && adj[cur][j] + dist[cur] < dist[j]) { dist[j] = adj[cur][j] + dist[cur]; } } } System.out.println(dist[n]); } private static int getMinIndex(int[] dist, boolean[] visited) { int min = Integer.MAX_VALUE; int index = -1; for (int i = 1; i < dist.length; i++) { if (!visited[i] && dist[i] < min) { min = dist[i]; index = i; } } return index; } static int nextInt() throws IOException { streamTokenizer.nextToken(); return (int) streamTokenizer.nval; } static long nextLong() throws IOException { streamTokenizer.nextToken(); return (long) streamTokenizer.nval; } }