SPFA 堆优化

ZORO · 2018-11-06 06:09:11 · 个人记录

堆优化

  #include<bits/stdc++.h>
#define N 200000 + 10
#define maxn 200000 + 10
#define INF 2147483647
using namespace std;
int dis[N],cnt,n,m,eu,ev,head[N],x,y,z,s;
bool vis[N];
struct Edge{
    int next,w,v;
}e[maxn];
inline void add(int u,int v,int w){
    e[++cnt].v=v;
    e[cnt].w=w;
    e[cnt].next=head[u];
    head[u]=cnt;
    return;
}
struct cmp{
    bool operator ()(int &x, int &y)
    {
        return dis[x] > dis[y];
    }
};
void spfa(int s)
{
    for(int i = 1; i <= n; i++) dis[i] = INF;
    dis[s]=0;
    priority_queue<int, vector<int>, cmp> q;
    q.push(s);
    vis[s]=1;
    while(!q.empty()){
        eu=q.top();
        q.pop();
        vis[eu]=0;
        for(int i=head[eu];i;i=e[i].next){
            ev=e[i].v;
            if(dis[eu]+e[i].w<dis[ev]){
                dis[ev]=dis[eu]+e[i].w;
                if(!vis[ev]){
                    vis[ev]=1;
                    q.push(ev);
                }
            }
        }
    }
}
inline int read() {
    char ch = getchar(); int u = 0, f = 1;
    while (!isdigit(ch)) {if (ch == '-')f = -1; ch = getchar();}
    while (isdigit(ch)) {u = u * 10 + ch - 48; ch = getchar();}
    return u * f;
}
int main()
{
    n = read(); m = read(); s = read();
    for(register int i=1;i<=m;i++)
    {
        x = read(), y = read(), z = read() ;
        add(x,y,z);
    }
    spfa(s);
    for(register int i=1;i<=n;i++) printf("%d ",dis[i]);
}