SGU 103 Traffic Lights

這題不具有負邊，而且越早到對之後越好，符合Dijkstra的貪婪特性

所以可以用它來實現此題，但問題在於必須計算在路口等待的時間（Wait函數）

int Wait(int a, int b, int t)

{

       if(color are the same) return 0;

       wt1 = next_color(a, t);

       wt2 = next_color(b, t);

       if(wt1 != wt2) return min(wt1, wt2);

       wt1 = next_color(a, wt1);

       wt2 = next_color(b, wt2);

       if(wt1 != wt2) return min(wt1, wt2); 

       wt1 = next_color(a, wt1);

       wt2 = next_color(b, wt2);

       if(wt1 != wt2) return min(wt1, wt2);

       return INF;

}

裡面有些其他的函數必須再自己實現，重要的是你只需要試三遍即可

若三遍都不可，那就是永遠都不行了

//By momo
#include<cstdio>
#include<queue>
#include<algorithm>

#define N 310
#define INF 999999999
#define PII pair<int,int> 
#define MP make_pair
#define F first
#define S second
#define FOR(it,c) for(__typeof((c).begin())it=(c).begin();it!=(c).end();it++)

using namespace std;

char clr[N][3];
int dis[N], prv[N];
int tme[N], tc[2][N];

vector<PII> G[N];
void add_edge(int a, int b, int l){
    G[a].push_back(MP(l, b));
    G[b].push_back(MP(l, a));
}

void get(int x, int tx, int& c, int& wt){
    
    int t[2];
    t[0] = tc[0][x], t[1] = tc[1][x];
    
    if(tx >= tme[x]){
        tx -= tme[x];
        tx %= (t[0] + t[1]);
        if(clr[x][0] == 'P'){
            if(tx < t[0]) c = 0, wt = t[0]-tx;
            else c = 1, wt = t[0]+t[1]-tx;
        }
        else{
            if(tx < t[1]) c = 1, wt = t[1]-tx;
            else c = 0, wt = t[0]+t[1]-tx;
        }
    }
    else{
        c = (clr[x][0] == 'B'? 0: 1);
        wt = tme[x] - tx;
    }
}

int wait(int a, int b, int t){
    int wt1, wt2, c1, c2;
    get(a, t, c1, wt1);
    get(b, t, c2, wt2);
    
    if(c1 == c2) return 0;
    
    if(wt1 != wt2) return min(wt1, wt2);
    
    wt1 += tc[c1^1][a];
    wt2 += tc[c2^1][b];
    if(wt1 != wt2) return min(wt1, wt2);
    
    wt1 += tc[c1][a];
    wt2 += tc[c2][b];
    if(wt1 != wt2) return min(wt1, wt2);
    
    return INF;
}

int s, t, n, m, ans[N], an;
priority_queue<PII> que;

int main(){
    
    scanf("%d%d%d%d", &s, &t, &n, &m); s--, t--;
    for(int i = 0; i < n; i++) scanf("%s%d%d%d", clr[i], &tme[i], &tc[0][i], &tc[1][i]);
    for(int i = 0; i < m; i++){
        int a, b, l;
        scanf("%d%d%d", &a, &b, &l);
        add_edge(a-1, b-1, l);
    }

    fill(dis, dis+n, INF);
    dis[s] = 0; prv[s] = -1;
    que.push(MP(-dis[s], s));
    while(!que.empty()){
        
        PII p = que.top(); que.pop(); p.F *= -1;
        if(dis[p.S] < p.F) continue;
        
        FOR(it, G[p.S]){
            
            int tx = wait(p.S, it->S, dis[p.S]) + dis[p.S] + it->F;
            if(tx < dis[it->S]){
                dis[it->S] = tx;
                prv[it->S] = p.S;
                que.push(MP(-dis[it->S], it->S));
            }

        }
    }

    if(dis[t] == INF) return puts("0"), 0;
    printf("%d\n", dis[t]);
    for(int p = t; p != -1; p = prv[p]) ans[an++] = p;
    while(an--) printf("%d%c", ans[an]+1, an==0?'\n':' ');
    
}