SGU-103 Traffic Lights

Problem Link

The Problem in short:
Given an undirected weighted graph where each node contains a traffic light. The light shows two colors: Blue and Purple. Blue is visible for t_b seconds and Purple is visible for t_p seconds. This keeps repeating periodically. These two values may differ for different nodes. Cars can cross an edge (u,v) iff both u and v has same color at the moment when the car departs from u to v.

Now, given a source S and a destination T and the initial state of every node (there current color and how much time is remaining for that color), calculate the minimum time to reach from S to T.

Solution:
Run Dijkstra's from S. The tricky part is: given a time t and a node u such that, the current time is t and the car is at u, when will the light at u and the light at v show the same color ?

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<ctype.h>
#include<assert.h>
#include<stdlib.h>
#include<time.h>

#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<iostream>
#include<algorithm>
#include<string>

using namespace std;

#define FOR(i,n) for(int i=0;i<(n);++i)
#define REP(i,a,b) for(int i=(a);i<=(b);++i)
#define CLR(a,x) memset(a,(x),sizeof(a))

typedef long long LL;
typedef pair<int,int> pii;

struct State {
    int at;
    int when;

    State(){}
    State(int _at, int _when){at = _at; when = _when;}

    bool operator < (const State other) const
    {
        return when > other.when;
    }
};

const int INF = (1<<29);

vector<int> adj[305];
int nodes, edges;
int cost[305][305];
int from,to;
int dist[305], parent[305];

int remaining[305], initColor[305], duration[305][2];

typedef pair<int,int> colorInfo;

colorInfo getColorInfo(int u, int t)
{
    if(t < remaining[u])
        return colorInfo(initColor[u],remaining[u]-t);

    int M = duration[u][0]+duration[u][1];
    int r = (t-remaining[u])%M;
    if(r < duration[u][1-initColor[u]])
        return colorInfo(1-initColor[u],duration[u][1-initColor[u]]-r);
    else
        return colorInfo(initColor[u],duration[u][initColor[u]]-(r-duration[u][1-initColor[u]]));
}

void getNext4InterestingTime(int u, int t, vector<int>& VT)
{
    VT.push_back(t);
    colorInfo info = getColorInfo(u,t);
    t += info.second;
    VT.push_back(t);

    FOR(i,4)
    {
        if(i%2==0)
            t += duration[u][1-info.first];
        else
            t += duration[u][info.first];

        VT.push_back(t);
    }
}

int calcTime(int u, int v, int t) // currently at u, current time t, want to go to v
{
    vector<int> interestingTime;

    getNext4InterestingTime(u,t,interestingTime);
    getNext4InterestingTime(v,t,interestingTime);

    sort(interestingTime.begin(),interestingTime.end());

    FOR(i,interestingTime.size())
    {
        if(getColorInfo(u,interestingTime[i]).first == getColorInfo(v,interestingTime[i]).first)
            return interestingTime[i];
    }

    return -1;
}

int solve()
{
    REP(i,1,nodes)
        dist[i] = INF;
    dist[from] = 0;
    parent[from] = from;

    State source(from,0);

    priority_queue<State> pq;
    pq.push(source);

    while(pq.empty()==false)
    {
        State u = pq.top();
        pq.pop();

        if(u.when > dist[u.at])
            continue;

        FOR(i,adj[u.at].size())
        {
            int x = adj[u.at][i];
            int y = calcTime(u.at,x,u.when);
            if(y == -1) continue;

            y += cost[u.at][x];
            if(dist[x] > y)
            {
                parent[x] = u.at;
                dist[x] = y;
                pq.push(State(x,y));
            }
        }
    }

    return dist[to];
}

int main()
{
    scanf("%d%d",&from,&to);
    scanf("%d%d",&nodes,&edges);

    FOR(i,nodes)
    {
        char s[5];
        scanf("%s%d%d%d",s,&remaining[i+1],&duration[i+1][0],&duration[i+1][1]);

        if(s[0]=='B')
            initColor[i+1] = 0;
        else
            initColor[i+1] = 1;
    }

    FOR(e,edges)
    {
        int u,v,w; scanf("%d%d%d",&u,&v,&w);
        adj[u].push_back(v);
        adj[v].push_back(u);
        cost[u][v] = cost[v][u] = w;
    }

    int ans = solve();

    if(ans >= INF)
    {
        puts("0");
    }
    else
    {
        vector<int> path;

        while(1)
        {
            path.push_back(to);
            if(to==from)
                break;
            to = parent[to];
        }

        cout<<ans<<"\n";

        for(int i=path.size()-1;i>=0;--i)
        {
            printf("%d",path[i]);
            if(i>0)
                printf(" ");
        }

        puts("");
    }

    return 0;
}