既然卡SPFA，那就用Dijkstra + 堆优化

我太菜了就不会SPFA

就是要注意，可能有些同学会说：

“我们又不是不会Dijkstra + 堆优化”

于是自信满满的交上，一看就傻眼了，，，

60分？！ #2 #3 TLE？！

这里就是一个需要注意的地方了

过不去可能是因为没有加一个简单的优化：（下面截取一部分代码） 

while (q.size()){
        int u = q.top().v;
        int d = q.top().u;
        q.pop();
        if(d!=dis[u])//这里是优化哦
            continue;//QAQ
        rep(i,u){
            int v = e[i].v;
            int w = e[i].w;
            if (dis[v] > dis[u] + w){
                dis[v] = dis[u] + w;
                node p;
                p.u = dis[v], p.v = v;
                q.push(p);
            }
        }
    }

这个优化把一些不可行的路径直接跳过去，会减少一些时间

没有这句是2500+ms

有这句只需208msQAQ

那么Dijkstra是不需要讲的（如果你做过弱化版）

堆优化似乎也不难，就是拿堆优化找最短dis就好

完整代码： 

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
#define go(i, j, n, k) for (int i = j; i <= n; i += k)
#define fo(i, j, n, k) for (int i = j; i >= n; i -= k)
#define rep(i, x) for (int i = h[x]; i; i = e[i].nxt)
#define mn 100010
#define inf 1 << 30
#define ll long long
#define ld long double
#define fi first
#define se second
#define root 1, n, 1
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
inline int read(){
    int f = 1, x = 0;char ch = getchar();
    while (ch > '9' || ch < '0'){if (ch == '-')f = -f;ch = getchar();}
    while (ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}
    return x * f;
}
inline void write(int x){
    if (x < 0)putchar('-');x = -x;
    if (x > 9)write(x / 10);
    putchar(x % 10 + '0');
}
//This is AC head above...
struct edge{
    int v, nxt, w;
} e[mn<<1];
int h[mn],p;
inline void add(int a,int b,int c){
    p++;
    e[p].nxt = h[a];
    h[a] = p;
    e[p].v = b;
    e[p].w = c;
}
struct node{
    int u,v;
    bool operator <(const node &b) const{
        return u > b.u;
    }
};
/*
bool operator <(const node &a,const node &b) {
        return a.u > b.u;
};
*/
int n,m,s;
int dis[mn];
priority_queue<node> q;
inline void Dij(int s){
    go(i, 0, n, 1)
        dis[i] = inf;
    dis[s] = 0;
    node o;
    o.u = 0;
    o.v = s;
    q.push(o);
    while (q.size()){
        int u = q.top().v;
        int d = q.top().u;
        q.pop();
        if(d!=dis[u])
            continue;
        rep(i,u){
            int v = e[i].v;
            int w = e[i].w;
            if (dis[v] > dis[u] + w){
                dis[v] = dis[u] + w;
                node p;
                p.u = dis[v], p.v = v;
                q.push(p);
            }
        }
    }
}
int main(){
    n=read(),m=read(),s=read();
    go(i,1,m,1){
        int u = read(), v = read(), w = read();
        add(u, v, w);
    }
    Dij(s);
    go(i,1,n,1){
        cout << dis[i] << " ";
    }
    cout << "\n";
    return 0;
}

第五次发题解，希望可以帮助一直爆60的同学