hdu2544-最短路 dijsktra

题目链接

Java代码

import java.util.*;

public class Main{
    // N表示路口 M表示路口之间的路线数量
    public static int N, M;
    // 用来装节点
    public static int [][] graph;
    // 用来挑出最小花费的节点
    public static PriorityQueue<Edge> queue;
    // 记录从起点到达那个点的花费
    public static int []dis;
    // 标记是否访问过
    public static boolean []vis;
    // 一个很大的常数
    public static int INF = 9999999;
    static class Edge{
        int x;
        int y;

        public Edge(int x, int y) {
            this.x = x;
            this.y = y;
        }

        public int getX() {
            return x;
        }


        public int getY() {
            return y;
        }

    }
    public static int dijsktra() {
        queue = new PriorityQueue<>(new Comparator<Edge>() {
            @Override
            public int compare(Edge o1, Edge o2) {
                return o1.getY() - o2.getY();
            }
        });
        // 将起点装进去
        queue.add(new Edge(1, 0));
        // 用来存Edge的类
        Edge now;
        // 记录起点到这个点的花费
        dis[1] = 0;
        // 如果队列中还有元素
        while (!queue.isEmpty()) {
            // 将其取出
            now = queue.poll();
            // 如果当前节点已经被访问
            if (vis[now.getX()]) {
                continue;
            }
            vis[now.getX()] = true;
            // 将当前能到达的点，及其花费记录下来
            for (int i = 1; i <= N; i++) {
                // 某节点没有被访问，当前节点达到某节点的花费，有减小,则更新到某节点的花费
                if (vis[i] == false && dis[now.getX()] + graph[now.getX()][i] < dis[i]) {
                    dis[i] = dis[now.getX()] + graph[now.getX()][i];
                    queue.add(new Edge(i, dis[i]));
                }
            }
        }
        return dis[N];
    }

    public static void init() {
        // 初始化
        vis = new boolean[N + 5];
        // 处理化记录数组
        dis = new int[N + 5];
        // 将dis中填充无穷大的数字
        Arrays.fill(dis, INF);
        // graph初始化
        graph = new int[N + 5][N + 5];
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                graph[i][j] = INF;
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (true) {
            N = sc.nextInt();
            M = sc.nextInt();
            // 退出条件
            if ( N == 0 && M == 0) {
                break;
            }

            init();

            int u, v, weight;
            for (int i = 0; i < M; i++) {
                u = sc.nextInt();
                v = sc.nextInt();
                weight = sc.nextInt();
                // 建立双向边 用数组的原因是因为可能有重复的数据
                // 比如 1 2 3，1 2 3
                graph[u][v] = graph[v][u] = weight;
            }

            System.out.println(dijsktra());
        }
    }
}

C/C++代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<string>
#define in(x) scanf("%d",&x)
#define out(x) printf("%d
",x)
#define rep(i,a,b) for(i=a;i<b;i++)
using namespace std;
const int maxn=105,inf=99999;
int n,m,i,j;
int dis[maxn],graph[maxn][maxn];
bool vis[maxn];
typedef pair<int,int> pa;
void dijkstra(int s)
{
    priority_queue<pa,vector<pa>,greater<pa> >q;
    dis[s]=0;
    q.push(pa(0,1));
    while(!q.empty()){
        pa p=q.top();
        q.pop();
        int vi=p.second;
        if(vis[vi]) continue;
        vis[vi]=true;
        rep(i,1,n+1){
            if(vis[i]==false&&dis[vi]+graph[vi][i]<dis[i]){
                dis[i]=dis[vi]+graph[vi][i];
                q.push(pa(dis[i],i));
            }
        }
    }
}
int main()
{
    int a,b,d;
    while(in(n),in(m),n||m){
    	fill(dis,dis+maxn,inf);
    	fill(graph[0],graph[0]+maxn*maxn,inf);
    	memset(vis,0,sizeof(vis));        
        rep(i,0,m){
            in(a),in(b),in(d);
            graph[a][b]=d;
            graph[b][a]=d;
        }
        dijkstra(1);
        out(dis[n]);
    }
}