SGU 103 Traffic Lights (最短路)

题意：/yylogo/archive//06/05/SGU-103.html

分析：比通常的最短路问题多了个限制条件，即每个路口的颜色必须相同时才能通过，否则需要等待。不难发现，路口的颜色是与当前已经花费的时间有关。于是可以构造一个函数，根据当前所用时间来计算某个路口的颜色，以及下一次变色所需时间。

利用该函数可以计算出当前两个路口的颜色，看其是否相同。如果不同，则再看其下一次变色所需时间是否相同，若相同，则仍然无法通过，再计算下下次变色时间，若仍相同，则该两个路口的颜色将一直相反，即无法相通。这里可以画图理解。也就是说，最多需要循环3次来判断两个路口颜色是否相同。

另外此题还需注意输入时若用scanf读取字符，需加上getchar()吸收回车，不然会RE。

#include<cstdio>#include<cstring>#include<algorithm>using namespace std;#define inf 0x3f3f3f3f#define N 305struct P{char c;int r,tb,tp;}p[N];int mp[N][N],d[N],pre[N];bool v[N];char color(int i,int d,int &t) //返回颜色以及下次变色的时刻{if(p[i].r>d){t=p[i].r-d;return p[i].c;}int x=d-p[i].r;x=x%(p[i].tb+p[i].tp);if(p[i].c=='P'){if(x<p[i].tb) { t=p[i].tb-x;return 'B';}else {t=p[i].tb+p[i].tp-x;return 'P';}}else{if(x<p[i].tp){t=p[i].tp-x;return 'P';}else {t=p[i].tb+p[i].tp-x;return 'B';}}}int wait(int a,int b,int d){int i,t1,t2,t=0;for(i=1;i<=3;++i){if(color(a,d,t1)==color(b,d,t2)) return t;t+=min(t1,t2);d+=min(t1,t2);}return inf;}int Dijkstra(int s,int e,int n){int j,i;for(i=1;i<=n;++i) d[i]=inf;d[s]=0;for(i=1;i<n;++i){int mi=inf,u=s;for(j=1;j<=n;++j)if(!v[j]&&d[j]<mi){u=j;mi=d[j];}v[u]=1;for(j=1;j<=n;++j)if(!v[j]&&mp[u][j]<inf){int t=wait(j,u,d[u]);if(d[u]+mp[u][j]+t<d[j]){d[j]=d[u]+mp[u][j]+t;pre[j]=u;}}}return d[e];}void output(int s,int e){if(s==e) {printf("%d",s);return;}output(s,pre[e]);printf(" %d",e);}int main(){int n,m,s,e,a,b,c,ans,i;scanf("%d%d%d%d",&s,&e,&n,&m);getchar();memset(mp,inf,sizeof(mp));for(i=1;i<=n;++i) {scanf("%c%d%d%d",&p[i].c,&p[i].r,&p[i].tb,&p[i].tp);getchar();}for(i=1;i<=m;++i) {scanf("%d%d%d",&a,&b,&c);mp[a][b]=mp[b][a]=c;}ans=Dijkstra(s,e,n);if(ans==inf) puts("0");else{printf("%d\n",ans);output(s,e);puts("");}return 0;}