Traffic Lights

题目描述

In the city of Dingilville the traffic is arranged in an unusual way. There are junctions and roads connecting the junctions. There is at most one road between any two different junctions. There is no road connecting a junction to itself. Travel time for a road is the same for both directions. At every junction there is a single traffic light that is either blue or purple at any moment. The color of each light alternates periodically: blue for certain duration and then purple for another duration. Traffic is permitted to travel down the road between any two junctions, if and only if the lights at both junctions are the same color at the moment of departing from one junction for the other. If a vehicle arrives at a junction just at the moment the lights switch it must consider the new colors of lights. Vehicles are allowed to wait at the junctions. You are given the city map which shows:

• the travel times for all roads (integers);
• the durations of the two colors at each junction (integers);
• and the initial color of the light and the remaining time (integer) for this color to change at each junction.

Your task is to find a path which takes the minimum time from a given source junction to a given destination junction for a vehicle when the traffic starts. In case more than one such path exists you are required to report only one of them.

题意概述

给定一张$N$个点$M$条边的图，每个点要么是蓝色要么是紫色，且会随着时间变化。可以从点$u$走到点$v$的条件是两点间有一条边且从$u$出发时$u, v$两点颜色相同。给定每个点的初始颜色以及两种颜色交替的时间，给定走过每条边所需的时间，求从$s$到$t$至少需要多少时间（可以在某个点停留）。

数据范围：$2 \le N \le 300, \ 1 \le M \le 14000$。

算法分析

显然这是一道最短路题，但在计算距离时有点不同。若走到点$u$的最短时间为$t$，打算更新点$v$，则需要计算出$t$之后最早的时刻$t’$满足$u, v$两点颜色相同，并用$t’+w_{u, v}$更新$v$。

寻找时刻$t’$可以直接暴力。有个显而易见的结论：如果在$t$之后，$u, v$同时改变颜色的次数超过连续$3$次，则$t’$不存在。

代码

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

struct IOManager {
  template <typename T>
  inline bool read(T &x) {
    char c; bool flag = false; x = 0;
    while (~ c && ! isdigit(c = getchar()) && c != '-') ;
    c == '-' && (flag = true, c = getchar());
    if (! ~ c) return false;
    while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar();
    return (flag && (x = -x), true);
  }
  inline bool read(char &c) {
    c = '\n';
    while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
    return ~ c;
  }
  inline int read(char s[]) {
    char c; int len = 0;
    while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
    if (! ~ c) return 0;
    while (isprint(c) && c != ' ') s[len ++] = c, c = getchar();
    return (s[len] = '\0', len);
  }
  template <typename T>
  inline IOManager operator > (T &x) {
    read(x); return *this;
  }
  template <typename T>
  inline void write(T x) {
    x < 0 && (putchar('-'), x = -x);
    x > 9 && (write(x / 10), true);
    putchar(x % 10 + '0');
  }
  inline void write(char c) {
    putchar(c);
  }
  inline void write(char s[]) {
    int pos = 0;
    while (s[pos] != '\0') putchar(s[pos ++]);
  }
  template <typename T>
  inline IOManager operator < (T x) {
    write(x); return *this;
  }
} io;

struct Junction { bool c; int r, t[2]; };

struct Edge { int v, l, nxt; };

struct Solver {
private:
  static const int N = 310;
  static const int M = 14010;
  int s, t, n, m, nume, h[N], dist[N], pre[N];
  bool in[N];
  Junction junc[N];
  Edge e[M << 1];
  void add_edge(int u, int v, int l) {
    e[++ nume] = (Edge) { v, l, h[u] }, h[u] = nume;
    e[++ nume] = (Edge) { u, l, h[v] }, h[v] = nume;
  }
  void input() {
    io > s > t > n > m;
    for (int i = 1; i <= n; ++ i) {
      char c; io > c > junc[i].r > junc[i].t[0] > junc[i].t[1], junc[i].c = c == 'P';
    }
    for (int i = 1; i <= m; ++ i) {
      int u, v, l; io > u > v > l, add_edge(u, v, l);
    }
  }
  int get(int u, int v, int t) {
    int cu = junc[u].c, tuu = 0, cv = junc[v].c, tvv = 0;
    if (t >= junc[u].r) {
      cu = ! cu; int cnt = (t - junc[u].r) / (junc[u].t[0] + junc[u].t[1]);
      tuu = junc[u].r + cnt * (junc[u].t[0] + junc[u].t[1]);
      if (tuu + junc[u].t[cu] <= t) tuu += junc[u].t[cu], cu = ! cu;
    }
    if (t >= junc[v].r) {
      cv = ! cv; int cnt = (t - junc[v].r) / (junc[v].t[0] + junc[v].t[1]);
      tvv = junc[v].r + cnt * (junc[v].t[0] + junc[v].t[1]);
      if (tvv + junc[v].t[cv] <= t) tvv += junc[v].t[cv], cv = ! cv;
    }
    if (cu == cv) return t;
    int cnt = 0;
    while (cu != cv) {
      if (cnt > 3) return 1e9;
      if (tuu + (tuu ? junc[u].t[cu] : junc[u].r) < tvv + (tvv ? junc[v].t[cv] : junc[v].r)) tuu += (tuu ? junc[u].t[cu] : junc[u].r), cu = ! cu;
      else if (tuu + (tuu ? junc[u].t[cu] : junc[u].r) > tvv + (tvv ? junc[v].t[cv] : junc[v].r)) tvv += (tvv ? junc[v].t[cv] : junc[v].r), cv = ! cv;
      else tuu += (tuu ? junc[u].t[cu] : junc[u].r), cu = ! cu, tvv += (tvv ? junc[v].t[cv] : junc[v].r), cv = ! cv, ++ cnt;
    }
    return max(tuu, tvv);
  }
  int spfa() {
    memset(dist, 0x7f, sizeof dist), dist[s] = 0;
    queue <int> que; que.push(s), in[s] = true;
    while (! que.empty()) {
      int u = que.front(); que.pop(), in[u] = false;
      for (int i = h[u]; i; i = e[i].nxt) {
        int t = get(u, e[i].v, dist[u]);
        if (dist[e[i].v] > t + e[i].l) {
          dist[e[i].v] = t + e[i].l, pre[e[i].v] = u;
          if (! in[e[i].v]) que.push(e[i].v), in[e[i].v] = true;
        }
      }
    }
    return dist[t];
  }
  void print(int t) {
    if (! t) return;
    print(pre[t]), io < t < ' ';
  }
  void process() {
    int dis = spfa();
    io < (dis < 1e9 ? dis : 0) < '\n';
    if (dis < 1e9) print(t), io < '\n';
  }

public:
  void solve() { input(), process(); }
} solver;

int main() {
  solver.solve();
  return 0;
}