http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2894
就因为粗心，一中午没A,题目说是2000000条边无向图，我数组却开了2000000真是该死，我一看别人A的状态，内存都比我大一倍，瞬间知道自己手残了，明明是4000000啊，
但令我不解的是说SPFA是BE的改良版，但为什么7100ms,虐心，完全坑爹。
#include <iostream> #include <stdio.h> #include <string.h> #include <stdlib.h> #define N 10000001 using namespace std; struct node { int x,y,w; }edge[4000002]; int dis[500002]; int n,m,s,e; int t,flag; void add(int x1,int y1,int w1) { edge[t].x=x1; edge[t].y=y1; edge[t++].w=w1; } void B() { for(int i=0;i<=n;i++) dis[i]=N; dis[s]=0; for(int i=1;i<=n-1;i++) { flag=0; for(int j=0;j<t;j++) { if(dis[edge[j].x]+edge[j].w<dis[edge[j].y]) { flag=1; dis[edge[j].y]=dis[edge[j].x]+edge[j].w; } } if(flag==0) break; } printf("%d ",dis[e]); } int main() { int xx,yy,zz; while(scanf("%d%d",&n,&m)!=EOF) { t=0; while(m--) { scanf("%d%d%d",&xx,&yy,&zz); add(xx,yy,zz); add(yy,xx,zz); } scanf("%d%d",&s,&e); B(); } return 0; } /************************************** Problem id : SDUT OJ 2894 User name : zlh130205张明成 Result : Accepted Take Memory : 49344K Take Time : 710MS Submit Time : 2014-06-27 13:32:27 **************************************/