最短路的应用,只不过路径的权值从单一的长度变成了各种耗费时间的和
#include <iostream> #include <cstdio> #include <string.h> using namespace std; const int maxn=300+10; const int maxm=(50000+10)*2; const int inf=200000000; int head[maxn],dis[maxn],vis[maxn],pre[maxn],re[maxn],ans[maxn]; int e[maxm],nextv[maxm],cost[maxm],loc[maxm]; int s,t,n,m; struct node { char c; int r,tb,tp; }; struct color { char c; int r; }; node light[maxn]; int min(int a,int b) { return a<b?a:b; } color getCol(int y, int time) { color tem; int did=light[y].r-time; if(did>0) { tem.c=light[y].c; tem.r=did; } else { did=-did; did=did%(light[y].tb+light[y].tp); if(light[y].c=='B') { if(did<light[y].tp) { tem.c='P'; tem.r=light[y].tp-did; } else { tem.c='B'; tem.r=light[y].tb-(did-light[y].tp); } } else { if(did<light[y].tb) { tem.c='B'; tem.r=light[y].tb-did; } else { tem.c='P'; tem.r=light[y].tp-(did-light[y].tb); } } } return tem; } int getT(int from,int to,int time,int flag) { if(flag>2) return -1; color c1=getCol(from,time),c2=getCol(to,time); if(c1.c==c2.c) return time; else if(c1.r==c2.r) return getT(from,to,time+c1.r,flag+1); else return time+min(c1.r,c2.r); } void dijkstra() { int i,j; for(i=1;i<=n;i++) { dis[i]=inf; vis[i]=0; } dis[s]=0; for(i=1;i<=n;i++) { int midv=inf,x=-1; for(j=1;j<=n;j++) { if(!vis[j]&&dis[j]<midv) midv=dis[x=j]; } if(x==-1||x==t) return; vis[x]=1; for(j=head[x];j!=-1;j=nextv[j]) { int y=loc[j]; if(!vis[y]) { int tem=getT(x,y,dis[x],0); if(tem==-1) continue; else { tem+=cost[j]; if(tem<dis[y]) { dis[y]=tem; pre[y]=x; } } } } } } void print(int tem) { int i=tem; int tot=0; while(i!=s) { ans[tot++]=i; i=pre[i]; } printf("%d ",s); if(tot>=1) for(i=tot-1;i>=0;i--) printf("%d ",ans[i]); } int main() { while(~scanf("%d%d",&s,&t)) { scanf("%d%d",&n,&m); getchar(); int i; char tc; for(i=1;i<=n;i++) { scanf("%c%d%d%d",&light[i].c,&light[i].r,&light[i].tb,&light[i].tp); getchar(); } memset(head,-1,sizeof(head)); int u,v,ti; int tot=0; for(i=1;i<=m;i++) { scanf("%d%d%d",&u,&v,&ti); loc[tot]=v; nextv[tot]=head[u]; head[u]=tot; cost[tot]=ti; tot++; loc[tot]=u; nextv[tot]=head[v]; head[v]=tot; cost[tot]=ti; tot++; } dijkstra(); if(dis[t]==inf) printf("0\n"); else { printf("%d\n",dis[t]); // print(pre[t]); //printf("%d\n",t); } } return 0; }