Dijkstra（单源最短路径有关问题）

Dijkstra（单源最短路径问题）

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int maxn = 1000;
const int INF = 0x7fffffff;

struct HeapNode {
    int d, u;
    bool operator < (const HeapNode& rhs) const {
        return d > rhs.d;
    }
};

struct Edge{
    int from, to, dist;
};

struct Dijkstra {
    int n, m;
    vector<Edge> edges;
    vector<int> G[maxn];
    bool done[maxn];
    int d[maxn];
    int p[maxn];
    void init(int n) {
        this->n = n;
        for(int i = 0; i < n; i++) { G[i].clear(); }
        edges.clear();
    }

    void AddEdge(int from, int to, int dist) {
        edges.push_back( (Edge) {from, to, dist} );
        m = edges.size();
        G[from].push_back(m-1);
    }

    void dijkstra(int s) {
        priority_queue<HeapNode> Q;
        for(int i = 0; i < n; i++) d[i] = INF;
        d[s] = 0;
        memset(done, 0, sizeof(done));
        Q.push((HeapNode){0, s});
        while(!Q.empty()) {
            HeapNode x = Q.top(); Q.pop();
            int u = x.u;
            if(done[u]) continue;
            done[u] = true;
            for(int i = 0; i < (int)G[u].size(); i++) {
                Edge& e = edges[G[u][i]];
                if(d[e.to] > d[u] + e.dist) {
                    d[e.to] = d[u] + e.dist;
                    p[e.to] = G[u][i];
                    Q.push((HeapNode){d[e.to], e.to});
                }
            }
        }
    }
};

Dijkstra t;

int main()
{
    int n, m;
    int start;
    int from, to, dist;
    scanf("%d%d", &n, &m);
    t.init(n);
    for(int i = 0; i < m; i++) {
        scanf("%d%d%d", &from, &to, &dist);
        t.AddEdge(from, to, dist);
    }
    cin >> start;
    t.dijkstra(start);
    for(int i = 0; i < n; i++) {
        cout << t.d[i] << ' ';
    }
    cout << endl;
    return 0;
}

/***********************
data:
6 9
0 2 5
0 3 30
1 0 2
1 4 8
2 1 15
2 5 7
4 3 4
5 4 18
5 3 10
0
***********************/