C++-POJ1502-MPI Maelstrom-[最短路][spfa][栈优化]

我不理解为什么写dijkska就WA呢？

atoi（）是个好东西，给你个颜色，自己体会

疑惑！疑惑！疑惑！

#include <queue>
#include <cstdio>
#include <algorithm>
using namespace std;
const int INF=1e9,MAXN=105,MAXM=10010;
int w(){char s[15];scanf("%s",s);return s[0]=='x'?INF:atoi(s);}
struct edge{
    int v,w,next;
    edge(int v=0,int w=0,int next=0):v(v),w(w),next(next){}
};
edge E[MAXM];int head[MAXN],cnt;
void add(int u,int v,int w){
    E[++cnt]=edge(v,w,head[u]),head[u]=cnt;
    E[++cnt]=edge(u,w,head[v]),head[v]=cnt;
}
int dis[MAXN],vis[MAXN],stack[MAXN],top;
int spfa(int s,int n){
    for(int i=1;i<=n;i++)vis[i]=0,dis[i]=INF;
    top=0,stack[++top]=1,vis[s]=1,dis[s]=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(dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;
                if(!vis[v])stack[++top]=v,vis[v]=1;
            }
    }
    int ans=0;
    for(int i=1;i<=n;i++)ans=max(ans,dis[i]);
    return ans;
}
int main(){
    int n;scanf("%d",&n);
    for(int i=2;i<=n;i++)for(int j=1;j<i;j++)add(i,j,w());
    printf("%d
",spfa(1,n));
    return 0;
}