题目链接：https://vjudge.net/contest/123674#problem/C
N题目大意是有n个点，然后给出从a点到b点的距离，a和b是互相可以抵达的，则是无向图，问从1到n的最短距离
解题思路：只是一道简单的最短路问题，按照最短路模板就能AC,但这题还有有个主意点，就是重边问题，但我用的是spfa算法，就不需要考虑这个问题，如果是dijkstra算法就要考虑这个问题；
ac代码：
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;
public class Main {
static int n, m;
static int[][] map = new int[][];
static int[] dis = new int[];
static boolean[] vis = new boolean[];
static final int Inf = 0x3f3f3f3f;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int u, v, w;
while (sc.hasNext()) {
m = sc.nextInt();n = sc.nextInt();
for (int i = ; i <= n; i++) {
for (int j = i; j <= n; j++) {
map[i][j] = Inf;
map[j][i] = Inf;
}
}
for (int i = ; i < m; i++) { //建图
u = sc.nextInt();
v = sc.nextInt();
w = sc.nextInt();
if (map[u][v] > w) { //spfa算法，已经考虑了重边问题，所以不需要再考虑
map[v][u] = w;
map[u][v] = w;
}
}
spfa();
System.out.println(dis[n]); //输出1~n的最短距离
}
sc.close();
}
private static void spfa(int s) { for (int i = ; i <= n; i++) {
vis[i] = false;
dis[i] = Inf;
}
dis[s] = ;
vis[s] = true;
Comparator<Integer> cmp = new Comparator<Integer>() { public int compare(Integer o1, Integer o2) {
int i = (int) o1;
int j = (int) ;
if (dis[i] > dis[j]) {
return ;
} else if (dis[i] == dis[j]) {
return ;
} else {
return -;
}
}
};
Queue<Integer> q = new PriorityQueue<Integer>(, cmp);
q.clear();
q.offer(s);
while (!q.isEmpty()) {
int head = q.poll();
vis[head] = false;
for (int i = ; i <= n; i++) {
int temp = dis[head] + map[head][i];
if (temp < dis[i]) {
dis[i] = temp;
if (!vis[i]) {
q.offer(i);
vis[i] = true;