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

import java.util.ArrayList;import java.util.PriorityQueue;import java.util.Scanner;public class Main {	PriorityQueue
   
     pq;	ArrayList
    
      []adj;	int []distTo;	int n, m;	public static void main(String[] args) {		new Main().run();	}	public void run() {		Scanner in = new Scanner(System.in);			while(in.hasNext()) {			n = in.nextInt();			m = in.nextInt();			if(n == 0 && m == 0) {				break;			}			distTo = new int[n+1];			pq = new PriorityQueue<>();			adj = new ArrayList[n+1];			for(int i = 1; i <= n; i++ ) {				adj[i] = new ArrayList<>();			}						for(int i = 0; i < m; i++ ) {				int u = in.nextInt();				int v = in.nextInt();				int w = in.nextInt();				adj[u].add(new Edge(u, v, w));				adj[v].add(new Edge(v, u, w));			}			dijkstra();			System.out.println(distTo[n]);			}			}	public void dijkstra() {		for(int i = 1; i <= n; i++ ) {			distTo[i] = Integer.MAX_VALUE;		}		distTo[1] = 0;		pq.offer(new dist(1, 0));				while(!pq.isEmpty()) {			int v = pq.poll().v;			for(Edge e: adj[v]) {				int w = e.v;				if(distTo[w] > distTo[v] + e.w) {					distTo[w] = distTo[v] + e.w;					pq.offer(new dist(w, distTo[w]));				}			}		}	}}		class Edge{	int u, v, w;	public Edge(int u, int v, int w) {		this.u = u;		this.v = v;		this.w = w;	}}class dist implements Comparable
     
      {//顶点v 与 与distTo[v]->w	int v;	int w;	public dist(int v, int w) {		this.v = v;		this.w = w;	}	public int compareTo(dist o) {		return w > o.w ? 1 : -1;	}}
     
    
   

临接矩阵的Dijkstra快速写法

for(int i = 1; i <= n; i++ ) {			dist[i] = map[1][i];		}		visit[1] = true;		while(true) {			int v = -1;			for(int u = 1; u <= n; u++ ) {				if(!visit[u] && (v == -1 || dist[u] < dist[v])) {					v = u;				}			}			if(v == -1)				break;			visit[v] = true;			for(int w = 1; w <= n; w++ ) {				if(map[v][w] < INF)					dist[w] = Math.min(dist[w], dist[v]+map[v][w]);			}		}

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