Dijkstra + 优先队列优化 模板

#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
#define INF 0x3F3F3F3F
using namespace std;

const int MAXN = (int)(1e3 + 10);
const int MAXM = (int)(1e4 + 10);

typedef pair<int, int> pii;
struct cmp{
    bool operator () (pii a, pii b){
        return a.first > b.first;
    }
};

int size, head[MAXN], point[MAXM], next[MAXM], val[MAXM];
int dis[MAXN], t, n;

void init()
{
        size = 0;
        memset(head, -1, sizeof head);
}

void add(int from, int to, int value)//单向边
{
        val[size] = value;
    point[size] = to;
    next[size] = head[from];
    head[from] = size++;
}

void dijkstra(int s)
{
    memset(dis, 0x3f, sizeof dis);
    priority_queue<pii, vector<pii>, cmp> q;
    q.push(make_pair(0, s));
    dis[s] = 0;
    while(!q.empty()){
        pii u = q.top();
        q.pop();
        if(u.first > dis[u.second]) continue;
        for(int i = head[u.second]; ~i; i = next[i]){
            int j = point[i];
            if(dis[j] > u.first + val[i]){
                dis[j] = u.first + val[i];
                q.push(make_pair(dis[j], j));
            }
        }
    }
}