Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
help!自己写的spfa+邻接表,为何RE?#include <iostream> using namespace std; const int maxx=(int)1e9,size=3000006; int stack[size*10]; typedef struct list { int value; int weight; struct list *next; }list; list *head[size],*rear[size]; void initlist(int n) { for(int i=1;i<n+1;i++) { head[i]=rear[i]=(list*)malloc(sizeof(list)); head[i]->next=NULL; head[i]->weight=0; } } void destroylist(int n) { for(int i=1;i<n+1;i++) while(head[i]) { rear[i]=head[i]->next; free(head[i]); head[i]=rear[i]; } } void enlistone(int a,int b,int c) { list *p; p=(list*)malloc(sizeof(list)); p->value=b; p->weight=c; p->next=NULL; rear[a]->next=p; rear[a]=p; head[a]->weight++; } void tralist(int a,int &h,int n,int *d,bool *in) { int b; int c; list *p; p=head[a]->next; while(p) { b=p->value; c=p->weight; if(d[a]+c<d[b]) { d[b]=d[a]+c; if(!in[b]) { stack[++h]=b; in[b]=1; } } p=p->next; } } void spfa(int vs,int n,int *shord) { int h=1,x,k,i; bool ifin[size]; for(i=1;i<n+1;i++) { stack[i]=ifin[i]=0; shord[i]=maxx; } shord[vs]=0; stack[h]=vs; ifin[vs]=1; while(h>0) { x=stack[h--]; ifin[x]=0; tralist(x,h,n,shord,ifin); } } int main() { int i,m,n,a,b,c,d; int x,shord[size]; while(cin>>n&&n) { scanf("%d%d%d%d",&a,&b,&c,&d); if(c) { d=d+n+2; b++; } else { b=b+n+2; d++; } initlist(2*n+2); for(i=1;i<n+1;i++) { scanf("%d",&x); enlistone(i,i+1,x); enlistone(i+1,i,x); } for(i=1;i<n+2;i++) { scanf("%d",&x); enlistone(i,i+1+n,x); enlistone(i+1+n,i,x); } for(i=n+2;i<2*n+2;i++) { scanf("%d",&x); enlistone(i,i+1,x); enlistone(i+1,i,x); } spfa(d,2*n+2,shord); destroylist(2*n+2); printf("%d\n",shord[b]); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator