SGU103 Traffic Lights

SGU103 Traffic Lights
제목 의 대의
무 방향 도 를 제시 합 니 다. 각 정점 에 신호등 이 하나 있 습 니 다. 일정한 주기 에 따라 변환 (왼쪽 닫 고 오른쪽 켜 기) 하 는 순간 에 한 변 두 점 의 색깔 이 같 으 면 통과 할 수 있 는 것 으로 간주 합 니 다. 필요 한 시간 은 변 의 가중치 질문 0 시간 은 s 에서 출발 하여 가장 빠 르 면 언제 t 에 도착 할 수 있 습 니까?
알고리즘 사고
발견 하기 어렵 지 않 습 니 다. 특정한 점 에 도착 하 는 시간 이 빠 를 수록 좋 습 니 다. 최 단 로 알고리즘 을 사용 하여 느슨 한 조작 에 대해 구 해 할 수 있 습 니 다. 먼저 dis [u] 부터 첫 번 째 색상 이 같은 시간 을 찾 을 수 있 습 니 다. 게다가 변 권 을 가 진 후에 dis [v] 를 업데이트 하 는 것 은 어렵 지 않 습 니 다. 대기 시간 은 최대 반주기 입 니 다. 그렇지 않 으 면 존재 하지 않 습 니 다. 대략적인 증명 은 다음 과 같 습 니 다.

v 의 주기 와 u 의 주기 가 길 면 결 과 는 한 주기 내 에 판정 할 수 있다

그렇지 않 으 면 v 주기 가 u 보다 짧 고 u 의 첫 번 째 주 기 를 고려 하여 먼저 신호등 을 켜 고 빨 간 신호등

을 가설 해도 무방 하 다.

u 가 녹색 신호등 일 때 v 에 녹색 신호등 이 나타 나 면 한 주기 에 똑 같은 시간

이 존재 한다.

그렇지 않 으 면 u 가 파란 불 일 때 v 는 반드시 빨 간 불 이 고 u 가 빨 간 불 일 때 주기 가 길지 않 기 때문에 v 는 반드시 빨 간 불 이 나타난다

이때 u 의 첫 번 째 주기 가 아직 끝나 지 않 았 기 때문에 한 반주기 안에 반드시 같은 시간 이 존재 한다

시간 복잡 도: SPFA - O (kE ∗ 200)
코드

/**
 * Copyright (c) 2015 Authors. All rights reserved.
 * 
 * FileName: 103.cpp
 * Author: Beiyu Li <sysulby@gmail.com>
 * Date: 2015-05-21
 */
#include <bits/stdc++.h>

using namespace std;

#define rep(i,n) for (int i = 0; i < (n); ++i)
#define For(i,s,t) for (int i = (s); i <= (t); ++i)
#define foreach(i,c) for (__typeof(c.begin()) i = c.begin(); i != c.end(); ++i)

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

const int inf = 0x3f3f3f3f;
const LL infLL = 0x3f3f3f3f3f3f3f3fLL;

const int maxn = 300 + 5;
const int maxe = 28000 + 5;

int psz;
struct Edge {
        int v, w;
        Edge *next;
} epl[maxe], *e[maxn];

void add_edge(int u, int v, int w)
{
        Edge *i = epl + psz++;
        i->v = v; i->w = w; i->next = e[u]; e[u] = i;
}

int n, m, s, t;
bool c[maxn];
int r[maxn], l[maxn][3];
int dis[maxn], pre[maxn];
bool inq[maxn];

int color(int u, int now)
{
        now = (now - r[u] + l[u][2]) % l[u][2];
        return now < l[u][c[u]^1]? c[u] ^ 1: c[u];
}

int calc(int u, int v, int now)
{
        For(i,now,now+300) if (color(u, i) == color(v, i)) return i;
        return inf;
}

void spfa()
{
        deque<int> deq;
        memset(dis, 0x3f, sizeof(dis));
        memset(inq, false, sizeof(inq));
        dis[s] = 0; inq[s] = true; deq.push_back(s);
        while (!deq.empty()) {
                int u = deq.front(); deq.pop_front(); inq[u] = false;
                for (Edge *i = e[u]; i; i = i->next) {
                        int v = i->v, w = calc(u, v, dis[u]) + i->w;
                        if (dis[v] <= w) continue;
                        dis[v] = w; pre[v] = u;
                        if (inq[v]) continue; inq[v] = true;
                        deq.empty() || dis[v] < dis[deq.front()]?
                                deq.push_front(v): deq.push_back(v);
                }
        }
}

void print(int u)
{
        if (u == s) { printf("%d", u + 1); return; }
        print(pre[u]); printf(" %d", u + 1);
}

int main()
{
        scanf("%d%d", &s, &t);
        --s; --t;
        scanf("%d%d", &n, &m);
        rep(i,n) {
                char buf[8];
                scanf("%s%d%d%d", buf, &r[i], &l[i][0], &l[i][1]);
                c[i] = (buf[0] == 'P');
                l[i][2] = l[i][0] + l[i][1];
        }
        while (m--) {
                int u, v, w;
                scanf("%d%d%d", &u, &v, &w);
                --u; --v;
                add_edge(u, v, w);
                add_edge(v, u, w);
        }
        spfa();
        if (dis[t] == inf) puts("0");
        else printf("%d
", dis[t]), print(t), puts("");

        return 0;
}