题目链接：https://vjudge.net/contest/123674#problem/C
N题目大意是有n个点，然后给出从a点到b点的距离，a和b是互相可以抵达的，则是无向图，问从1到n的最短距离
解题思路：只是一道简单的最短路问题，按照最短路模板就能AC,但这题还有有个主意点，就是重边问题，但我用的是spfa算法，就不需要考虑这个问题，如果是dijkstra算法就要考虑这个问题；
ac代码：
1 import java.util.Comparator; 2 import java.util.PriorityQueue; 3 import java.util.Queue; 4 import java.util.Scanner; 5 public class Main { 6 static int n, m; 7 static int[][] map = new int[1001][1001]; 8 static int[] dis = new int[1001]; 9 static boolean[] vis = new boolean[1001]; 10 static final int Inf = 0x3f3f3f3f; 11 public static void main(String[] args) { 12 Scanner sc = new Scanner(System.in); 13 int u, v, w; 14 while (sc.hasNext()) { 15 m = sc.nextInt();n = sc.nextInt(); 16 for (int i = 1; i <= n; i++) { 17 for (int j = i; j <= n; j++) { 18 map[i][j] = Inf; 19 map[j][i] = Inf; 20 } 21 } 22 for (int i = 0; i < m; i++) { //建图 23 u = sc.nextInt(); 24 v = sc.nextInt(); 25 w = sc.nextInt(); 26 if (map[u][v] > w) { //spfa算法，已经考虑了重边问题，所以不需要再考虑 27 map[v][u] = w; 28 map[u][v] = w; 29 } 30 } 31 spfa(1); 32 System.out.println(dis[n]); //输出1~n的最短距离 33 } 34 sc.close(); 35 } 36 private static void spfa(int s) { 37 38 for (int i = 1; i <= n; i++) { 39 vis[i] = false; 40 dis[i] = Inf; 41 } 42 dis[s] = 0; 43 vis[s] = true; 44 Comparator<Integer> cmp = new Comparator<Integer>() { 45 46 public int compare(Integer o1, Integer o2) { 47 int i = (int) o1; 48 int j = (int) 02; 49 if (dis[i] > dis[j]) { 50 return 1; 51 } else if (dis[i] == dis[j]) { 52 return 0; 53 } else { 54 return -1; 55 } 56 } 57 }; 58 Queue<Integer> q = new PriorityQueue<Integer>(1001, cmp); 59 q.clear(); 60 q.offer(s); 61 while (!q.isEmpty()) { 62 int head = q.poll(); 63 vis[head] = false; 64 for (int i = 1; i <= n; i++) { 65 int temp = dis[head] + map[head][i]; 66 if (temp < dis[i]) { 67 dis[i] = temp; 68 if (!vis[i]) { 69 q.offer(i); 70 vis[i] = true; 71