| ||||||||||
| 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 | |||||||||
附一spfa丑陋代码!!!!#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <stack>
#include <queue>
#define inf 0x3f3f3f3f
#define M 110
#define ll __int64
using namespace std;
int end[M<<4],start[M<<4],next[M<<4],cost[M<<4],edge_num;
inline void Init(){
edge_num=0;
memset(start,-1,sizeof(start));
}
inline void add_edge (int u,int v ,int w){
end[edge_num]=v;
cost[edge_num]=w;
next[edge_num]=start[u];
start[u]=edge_num++;
}
bool visite[M]; int dist[M],cnt[M];
void spfa(int st,int n){
memset(visite,false,sizeof(visite));
memset(cnt,0,sizeof(cnt));
memset(dist,inf,sizeof(dist));
queue<int> my_queue; int u,v,w;
my_queue.push(st),visite[st]=true;
cnt[st]++,dist[st]=0;
while(!my_queue.empty()){
u=my_queue.front(),my_queue.pop(),visite[u]=false;
for(int i=start[u];i!=-1;i=next[i]){
v=end[i]; w=cost[i];
if(dist[v]>dist[u]+w){
dist[v]=dist[u]+w;
if(!visite[v]){
visite[v]=true;
my_queue.push(v);
if(++cnt[v]>n) return;
}
}
}
}
return;
}
int main(){
int n,start_position,end_position,k,edge;
while(~scanf("%d%d%d",&n,&start_position,&end_position)){
Init();
for(int i=1;i<=n;i++){
scanf("%d",&k);
for(int j=1;j<=k;j++){
scanf("%d",&edge);
if(j!=1) add_edge(i,edge,1);
else add_edge(i,edge,0);
}
}
spfa(start_position,n);
if(dist[end_position]==inf) puts("-1");
else printf("%d\n",dist[end_position]);
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator