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