SGU 103 Traffic Lights [最短路]

传送门 http://acm.sgu.ru/problem.php?contest=0&problem=103
题意：有一个无向图，n个结点m条边，每个结点上都有一个交通灯，灯有蓝和紫两种颜色，边u->v能走的条件是出发的时候u v两地灯颜色相同。交通灯初始是一种给定的颜色，持续r秒，然后开始循环改变，蓝色持续Cb秒紫色持续Cp秒。现给每个灯的变换情况以及每条路的通过时间，问从S点到T点的最短时间及路线。注意如果正处于灯光变换的瞬间应按新的灯光判断。

这题注意在于计算每条路的通过时间，除了它固有的时间外，还要计算一个等灯的时间。若某时刻uv两点颜色不同，则这条路能走的时间一定是接下来某一次变灯的时候，若连续变灯3次仍不满足，则此路不通。
接下来用dijkstra就能搞定的了。

此题有一个坑是S可能走不到T（也许不连通也许灯不允许），此时什么都不输出即可。

#include<cassert>
#include<iostream>
#include<cstdio>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
using namespace std;

#define rep(i,f,t) for(int i = (f),_end = (t); i <= _end; ++i)
#define clr(c,x) memset(c,x,sizeof(c));
#define debug(x) cout<<"debug "<<x<<endl;

const int INF = 0x3f3f3f3f;
const int maxn = 303;
typedef pair<int,int> Pr;
typedef vector<Pr> Vec;

Vec G[maxn];
const int B = 1,P = 0;//两种灯
int r[maxn],b[maxn],p[maxn],c[maxn];
int prev[maxn];
int tm[maxn];
int n,m;
int S,T;
bool vis[maxn];

void out(){
    stack<int> sta;
    int i = T;
    while(i){
        sta.push(i);
        i = prev[i];
    }
    printf("%d
",tm[T]);
    while(!sta.empty()){
        printf("%d",sta.top());
        sta.pop();
        putchar(sta.empty() ? '
' : ' ');
    }
}

//计算i点在t时间的灯的颜色
int color(int i,int t){
    if(t < r[i])return c[i];
    t -= r[i];
    t %= (b[i]+p[i]);
    if(c[i]==B){
        return (t<p[i] ? P : B);
    }else{
        return (t<b[i] ? B : P);
    }
}

//计算i点下一次变灯的时间
int nextChange(int i,int t){
    if(t < r[i])return r[i];
    int t2 = (t-r[i]) % (p[i]+b[i]);
    if(c[i]==B){
        if(t2<p[i])return t+p[i]-t2;
        t2 -= p[i];
        return t+b[i]-t2;
    } else {
        if(t2<b[i])return t+b[i]-t2;
        t2 -= b[i];
        return t+p[i]-t2;
    }
}

//通过i--j需要等的时间
int cal(int i,int j,int t){
    if(color(i,t)==color(j,t))return 0;
    int cng = 3; //最多计算3次
    int t1 = t,t2 = t;
    while(cng--){
        t1 = nextChange(i,t1);
        t2 = nextChange(j,t2);
        if(t1 != t2){
            int mt = min(t1,t2);
            assert(color(i,mt) == color(j,mt));
            return mt-t;
        }
    }
    return INF; //两个灯永远不会相同
}

void solve(){
    priority_queue<Pr,vector<Pr>,greater<Pr> > q;
    clr(tm,INF);
    q.push(Pr(0,S));
    while(!q.empty()){
        int u = q.top().second;
        int d = q.top().first;
        q.pop();
        if(vis[u])continue;
        vis[u] = true;
        if(u==T){
            out();
            return;
        }
        rep(i,0,G[u].size()-1){
            int v = G[u][i].first;
            if(vis[v])continue;
            int tmp = cal(u,v,d);
            if(tmp == INF)continue;//无法通过
            tmp += G[u][i].second;//等灯+走到对面的时间
            if(d+tmp < tm[v]){
                tm[v] = d+tmp;
                prev[v] = u;
                q.push(Pr(tm[v], v));
            }
        }
    }
}

int main(){
    scanf("%d%d",&S,&T);
    scanf("%d%d",&n,&m);
    rep(i,1,n){
        char ctmp;
        scanf(" %c%d%d%d",&ctmp,r+i,b+i,p+i);
        c[i] = (ctmp=='B'?B:P);
    }
    rep(i,1,m){
        int f,t,v;
        scanf("%d%d%d",&f,&t,&v);
        G[f].push_back(Pr(t,v));
        G[t].push_back(Pr(f,v));
    }
    solve();
    return 0;
}