Dijkstra算法模板

 

#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#define maxn 500       //图的规模
#define INF 1<<30
using namespace std;

struct Edge {           //存放边的信息 dist为距离
       int from,to,dist;
};

struct HeapNode {         //算法用到的优先队列的节点
       int d, u;
       bool operator < (const HeapNode& rhs) const {
              return d > rhs.d;
       }
};

struct Dijkstra {
       int n, m;              //点数和边数
       vector<Edge> edges;    //边列表
       vector<int> G[maxn];   //每个节点出发的边编号 从0开始
       bool done[maxn];       //是否已经永久标号
       int d[maxn];           //s 到各个点的距离
       int p[maxn];           //最短路上的一条边

       void init(int n) {       //n为图中节点个数
              this->n = n;
              for(int i = 0; i < n; i++) G[i].clear();   //清空邻接表
              edges.clear();                            //清空边表
       }

       void AddEdge(int from, int to, int dist) {
              //如果是无向图，每条边需要调用两次AddEdge
              edges.push_back((Edge){from, to, dist});
              m = edges.size();
              G[from].push_back(m-1);
       }

       void dijkstra(int s) {                   //求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 < 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});
                            }
                     }
              }
       }
};