C++-POJ2159-Candies[spfa][栈优化][邻接表]

#include <cstdio>
const int M=150010,N=30010;
struct edge{int v,w,next;}e[M];int head[N],cnt;
void add(int u,int v,int w){e[++cnt].v=v,e[cnt].w=w,e[cnt].next=head[u],head[u]=cnt;}
int d[N],vis[N],stack[M],top;
int spfa(int n){
    for(int i=1;i<=n;i++)vis[i]=0,d[i]=2147483647;
    top=0,stack[++top]=1,vis[1]=1,d[1]=0;
    for(int u;top>=0;){
        u=stack[top--],vis[u]=0;
        for(int i=head[u],v,w;v=e[i].v,w=e[i].w,i;i=e[i].next)
            if(d[v]>d[u]+w){
                d[v]=d[u]+w;
                if(!vis[v])stack[++top]=v,vis[v]=1;
            }
    }
    return d[n];
}
int main(){    
    for(int n,m,u,v,w;scanf("%d%d",&n,&m)!=EOF;){
        for(int i=1;i<=n;i++)head[i]=0;
        while(m--)scanf("%d%d%d",&u,&v,&w),add(u,v,w);
        printf("%d
",spfa(n));        
    }
    return 0;
}