本文共 2065 字，大约阅读时间需要 6 分钟。
http://acm.sgu.ru/problem.php?contest=0&problem=103
简单的最短路 不过在处理等待时间上有点繁琐
代码：
#include #include #include #include #include #include #include #include #include #include #include #define ll long longusing namespace std;const int INF=0x3f3f3f3f;const int N=305;int dist[N],pre[N];int d[N][N];bool had[N];struct node{ char c; int r,tb,tp;}mem[N];void M(int t,char &c,int &r,int tb,int tp){ if(t<=r) {r=r-t+1;return ;} t=(t-r)%(tb+tp); if(t==0) { if(c=='B') {c='B';r=1;} else {c='P';r=1;} return ; } if(c=='P') { if(t<=tb) {r=tb-t+1;c='B';} else {r=(tp-(t-tb))+1;c='P';} }else { if(t<=tp) {r=tp-t+1;c='P';} else {r=(tb-(t-tp))+1;c='B';} }}int F(int t,int l,int r){ char lc=mem[l].c,rc=mem[r].c; int lr=mem[l].r,ltb=mem[l].tb,ltp=mem[l].tp; int rr=mem[r].r,rtb=mem[r].tb,rtp=mem[r].tp; M(t,lc,lr,ltb,ltp); M(t,rc,rr,rtb,rtp); if(lc==rc) return 0; if(lr==rr&<b==rtp&<p==rtb) return INF; if(lr!=rr) return min(lr,rr); int tmp=lr; if(lc=='B') {lc='P';lr=ltp;} else {lc='B';lr=ltb;} if(rc=='B') {rc='P';rr=ltp;} else {rc='B';rr=rtb;} if(lr!=rr) return tmp+min(lr,rr); tmp+=lr; if(lc=='B') {lc='P';lr=ltp;} else {lc='B';lr=ltb;} if(rc=='B') {rc='P';rr=ltp;} else {rc='B';rr=rtb;} if(lr!=rr) return tmp+min(lr,rr); return INF;}int dijkstra(int x1,int x2,int n){ memset(had,false,sizeof(had)); for(int i=1;i<=n;++i) dist[i]=INF; dist[x1]=0; pre[x1]=x1; for(int w=1;w<=n;++w) { int k=-1; for(int i=1;i<=n;++i) if(!had[i]&&(k==-1||dist[i] dist[k]+d[k][i]+tmp) { dist[i]=dist[k]+d[k][i]+tmp; pre[i]=k; } } } return dist[x2];}int main(){ //freopen("data.in","r",stdin); int x1,x2; while(cin>>x1>>x2) { int n,m; cin>>n>>m; for(int i=1;i<=n;++i) cin>>mem[i].c>>mem[i].r>>mem[i].tb>>mem[i].tp; for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) if(i==j) d[i][j]=0; else d[i][j]=INF; while(m--) { int l,r,len; cin>>l>>r>>len; d[l][r]=len; d[r][l]=len; } int T=dijkstra(x1,x2,n); if(T==INF) cout<<"0"<
转载于:https://www.cnblogs.com/liulangye/archive/2013/04/19/3031225.html