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 90 2 50 3 301 0 21 4 82 1 152 5 74 3 45 4 185 3 100***********************/