![Dijkstra + 优先队列优化 模板 Dijkstra + 优先队列优化 模板](https://image.shishitao.com:8440/aHR0cHM6Ly9ia3FzaW1nLmlrYWZhbi5jb20vdXBsb2FkL2NoYXRncHQtcy5wbmc%2FIQ%3D%3D.png?!?w=700&webp=1)
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
#define INF 0x3F3F3F3F
using namespace std; const int MAXN = (int)(1e3 + );
const int MAXM = (int)(1e4 + ); 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 = ;
memset(head, -, 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(, s));
dis[s] = ;
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));
}
}
}
}