其实hihocoder里的题目目前大都是模板题啊-。-

这周的是SPFA，暑假的时候有看过SPFA，不过一直用的都是Dijkstra，感觉spfa要更加简洁一点~~，今天找了一份之前一直都看不太懂所以就没怎么用的模板==，今天耐下心来观摩最终还是看懂了hh。

============================================================

所以以后都用spfa吧~~~速度快&&避开了stl~~，写这个bolg主要是拿来记录模板的

#include <cstdio>#include <iostream>#include <queue>#include <algorithm>#include <cstring>using namespace std;typedef long long LL;const int maxn = 191111;//最大点数const int maxe = maxn*20;//最大边数int head[maxn];//记录点的头int to[maxe],cost[maxe],next[maxe];//记录边的两边断点，边长；int n,m,st,ed,ecnt;//点数，边数，起始点，结束点，边数记录void init() {//初始化    memset(head,0,sizeof(head));    ecnt = 1;}void add_edge(int u,int v,int c) {//添加边，姿势类似于链表的添加，是单向边，如果 是无向边的话要反向添加一次边    to[ecnt] = v;cost[ecnt] = c;next[ecnt] = head[u];head[u] =ecnt++;}LL dis[maxn];//每个点到起始点的最短距离bool vis[maxn];//记录该点是否在更新当中的队列中void SPFA() {    memset(dis,0x3f3f,sizeof(dis));    memset(vis,0,sizeof(vis));    queue<int> que; que.push(st);    dis[st] = 0;    while(!que.empty()) {        int u = que.front(); que.pop();        vis[u] = false;        for(int p = head[u];p;p = next[p]) {            int &v = to[p];            if(dis[v]==-1||dis[v] > dis[u] + cost[p]) {                    dis[v] = dis[u] + cost[p];                    if(!vis[v]) que.push(v);//如果不在更新队列中，将该点加入                    vis[v] = true;//加入更新队列当中            }        }    }}int main() {    scanf("%d%d%d%d",&n,&m,&st,&ed);    init();    while(m--) {        int a,b,c;        scanf("%d%d%d",&a,&b,&c);        add_edge(a,b,c);        add_edge(b,a,c);    }    SPFA();    printf("%d\n",dis[ed]);    return 0;}

hihocoder 第二十五周 spfa 最短路