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 |
bellman单源最短路径的思路,WA! 望高人指点。(内含代码)#include <stdio.h> #include <string.h> #define VN 303 #define AN 28003 #define MAX 900000000 int remaind[VN],du[VN][2]; int dis[VN]; typedef struct { int arcnum; int vexnum; int gra[VN][VN]; //gra[i][j]记录从i到j的时间 }graph; graph G; int arc[AN][2]; //记录第i个灯B和P颜色的周期,B存于arc[i][0],P存于varc[i][1] int light[VN]; //记录起始时各灯的颜色,0:B 1:P int begin,end; //起始位置和终止位置 int tim(int from,int to,int ti) { //返回从from到to点需要花费的时间,如果不可达则返回-1 int a,b,p,ff,tt; int re1,re2,ll1,ll2; tt=ti; b=du[from][0]; p=du[from][1]; ll1=light[from]; re1=remaind[from]; /////////////////////////// if(ti<re1) { re1=re1-ti; } else { ti-=re1; ti=ti%(p+b); if(ll1==0) a=p; else a=b; if(ti<a) { re1=a-ti; ll1=(ll1+1)%2; } else { re1=b+p-ti; } } ti=tt; b=du[to][0]; p=du[to][1]; ll2=light[to]; re2=remaind[to]; if(ti<re2) { re2=re2-ti; } else { ti-=re2; ti=ti%(p+b); if(ll2==0) a=p; else a=b; if(ti<a) { re2=a-ti; ll2=(ll2+1)%2; } else { re2=b+p-ti; } } //到这里求出时间ti时,from点和to点的灯的颜色和剩余时间 if(ll1==ll2) //如果颜色相同则返回走路的时间 return G.gra[from][to]; else if(re1!=re2) //如果颜色不同,灯改变颜色的剩余时间不同 { //返回两者较小的+走路时间 a=re1; if(re2<re1) a=re2; return a+G.gra[from][to]; } else //如果剩余时间相同,两个灯的下个颜色的周期不同 { //返回剩余时间+较小的周期+走路时间 ll1=(ll1+1)%2; ll2=(ll2+1)%2; if(du[from][ll1]!=du[to][ll2]) { a=du[from][ll1]; if(du[from][ll1]>du[to][ll2]) a=du[to][ll2]; return a+re1+G.gra[from][to]; } else //如果下一个周期相同,再下一个周期不同 { //返回剩余时间+下一个周期的时间+再下一个周期中较小的时间+走路时间 ff=du[from][ll1]; ll1=(ll1+1)%2; ll2=(ll2+1)%2; if(du[from][ll1]!=du[to][ll2]) { a=du[from][ll1]; if(du[from][ll1]>du[to][ll2]) a=du[to][ll2]; return ff+a+re1+G.gra[from][to]; } else return -1; //如果仍然相同,则不可以通过,返回-1 } } } void bellman() { //单源最短路径的bellman-ford算法 int i,j,k; bool sign; for(i=0;i<=G.vexnum;i++) dis[i]=MAX; dis[begin]=0; sign=true; for(i=1;i<=G.vexnum && sign;i++) { sign=false; for(j=1;j<=G.arcnum;j++) { if(dis[arc[j][0]]<MAX) { k=tim(arc[j][0],arc[j][1],dis[arc[j][0]]); if(dis[arc[j][1]]>dis[arc[j][0]]+k) { dis[arc[j][1]]=dis[arc[j][0]]+k; sign=true; } } } } } int main() { int i,k,m,n; int b,e,v; char s[5]; int po,cb,cp; scanf("%d%d",&begin,&end); scanf("%d%d",&n,&m); memset(&G,0,sizeof(graph)); G.vexnum=n; G.arcnum=2*m; for(i=1;i<=n;i++) { scanf("%s%d%d%d",s,&po,&cb,&cp); if(s[0]=='B') light[i]=0; else light[i]=1; remaind[i]=po; du[i][0]=cb; du[i][1]=cp; } k=1; for(i=0;i<m;i++) { scanf("%d%d%d",&b,&e,&v); arc[k][0]=b; arc[k][1]=e; G.gra[b][e]=v; k++; arc[k][0]=e; arc[k][1]=b; G.gra[e][b]=v; k++; } bellman(); if(dis[end]==MAX) printf("0\n"); else printf("%d\n",dis[end]); return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator