本文共 1506 字，大约阅读时间需要 5 分钟。

import java.util.LinkedList;import java.util.Queue;import java.util.Scanner;public class Main {	static boolean []visit;	static int []u;	static int []v;	static int []w;	static int []head;	static int []next;	static int []dist;	static int m, n;	static int INF = 99999999;	static Queue
   
     que;	public static void main(String[] args) {		Scanner in = new Scanner(System.in);		while(in.hasNext()) {			n = in.nextInt();			m = in.nextInt();			if(n == 0 && m == 0)				break;			u = new int[2*m+1];//边数多一 因为从1开始			v = new int[2*m+1];			w = new int[2*m+1];			next = new int[2*m+1];						dist = new int[n+1];//顶点多一			head = new int[n+1];			visit = new boolean[n+1];			que = new LinkedList<>();			for(int i = 0; i <= n; i++ ) {				head[i] = -1;			}			for(int i = 1; i <= m; i++ ) {				u[i] = in.nextInt();				v[i] = in.nextInt();				w[i] = in.nextInt();				next[i] = head[u[i]];				head[u[i]] = i;			}			for(int i = m+1; i <= 2*m; i++ ) {//构建 无向图				u[i] = v[i-m];				v[i] = u[i-m];				w[i] = w[i-m];				next[i] = head[u[i]];				head[u[i]] = i;			}			spfa();			System.out.println(dist[n]);		}			}	public static void spfa() {		for(int i = 1; i <= n; i++ ) {			dist[i] = INF;		}		dist[1] = 0;		visit[1] = true;		que.offer(1);		while(!que.isEmpty()) {			int from = que.poll();			visit[from] = false;//出队后 标记为未访问			int k = head[from];			while(k != -1) {				if(dist[v[k]] > dist[u[k]] + w[k]) {					dist[v[k]] = dist[u[k]] + w[k];					if(!visit[v[k]]) {						que.offer(v[k]);					}				}				k = next[k];//寻找下一条边				}		}	}}
   

转载地址：http://vlimi.baihongyu.com/