单源最短路模板
一：SPFA
const int N = 1001; //点using namespace std;struct node{int l,dir;}w;//边struct In{int idx;int l;bool friend operator<(const In &a, const In &b){return a.l > b.l;}}ww,zz;//bfsvector<node>mmap[N];priority_queue<In>q;int dis[N];int start, end; //start 起点, end 终点int nodenum;//点数 = endint n, m;int base;void init(){while (!q.empty())q.pop();int i;for (i = 0; i <= nodenum; i++){dis[i] = -1;mmap[i].clear();}return;}inline void creat(int s, int e, int value) {w.l = value;w.dir = e;mmap[s].push_back(w);return;}void dij(){int i, j;ww.idx = start;ww.l = 0;int size = 0;node now;q.push(ww);while (!q.empty()){ww = q.top();q.pop();if (dis[ww.idx] != -1)continue;dis[ww.idx] = ww.l;if(ww.idx == end)return;size = mmap[ww.idx].size();for (i = 0;i < size; i++){now = mmap[ww.idx][i];zz.idx = now.dir;zz.l = ww.l + now.l;if(dis[zz.idx] == -1){q.push(zz);}}}return;}