| ||||||||||
| 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