P3011 [USACO11JAN] Traffic Lights S
目录题目
题目描述
和FJ靠的最近的城市Kenosha市有 \(M\)条道路。(编号为\(1-M\)) 连接着\(N\)个路口 (编号为\(1-N\)) 。保证没有重边和自环。
从点\(i\)到点\(j\)需要的时间是\(T_{ij}\)， 且保证\(T_{ij}\) = \(T_{ji}\)
每个路口有一个交通灯，有两种颜色：蓝色和紫色。两个颜色周期性的交替。蓝色持续一定时间，然后紫色持续一定时间。
想要从\(i\)到\(j\)只有在\(i\)和\(j\)的信号灯颜色相同的时候才可以走(从T1离开i走向j，只需T1时刻i与j的颜色相同即可，无其他任何约束。)
如果在变幻灯的那一秒到\(j\)，考虑的是变幻后的颜色。
给你所有第\(i\)个路口的蓝色灯持续时间\(DB_i\)和紫色灯持续时间\(DP_i\)
和每个路口刚开始灯的颜色\(C_i\),剩余持续时间\(R_i\)
求一个给定的原点\(S\)到给定目标点\(D\)的最小时间。
输入输出格式
输入格式
- 第一行两个整数 S和D
- 第二行两个整数 N和M
- 第三至N+2行。第i+2行描述点i的信号灯情况 \(C_i\), \(R_i\), \(DB_i\), \(DP_i\)
- 第三道N+M+2行：第N+2+k行描述第k条道路 : \(i\), \(j\), \(T_{ij}\)
输出格式
- 一个整数代表从S到D最少消耗的时间， 如果S、D不连通，输出0
感谢@ToBiChi 提供翻译
题目描述
Kenosha, the city nearest Farmer John, has M (1 <= M <= 14,000) roads conveniently numbered 1..M that connect N (2 <= N <= 300) junctions which are conveniently numbered 1..N. No two roads connect the same pair of junctions. No road connects a junction to itself. The integer travel time T_ij (1 <= T_ij <= 100) between junctions i and j is the same for both directions (i.e., T_ij = T_ji).
Each junction has a single traffic light with two colors: blue or purple. The color of each light alternates periodically: blue for certain duration and then purple for another duration. Traffic is permitted to commence 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. The lights do not necessarily have to be the same on the whole trip down the road.
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:
Init Remg Blue Purple
4 76 Junction Color Time Cycle Cycle
>>[1B]===[2P]====== 1 B 2 16 99
| / \ 2 P 6 32 13
40| /75 \ 3 P 2 87 4
| / \ 4 P 38 96 49
[3P]===============[4P]>>
77
* The travel times T_ij for all roads
* The durations of the two colors at junction i. (DB_i (1 <= DB_i <= 100) for the blue light and DP_i (1 <= DP_i <= 100) for the purple light)
* The initial color C_i of the light at junction i (a letter 'B' or 'P' with the obvious meaning) and the remaining time R_i (1 <= R_i <= 100) for this color to change
Find the minimum time one needs to get from a given source S (1 <= S <= N) to a given destination D (1 <= D <= N; D != S).
Consider the map below with four junctions and five roads. FJ wants to travel from junction 1 to junction 4. The first light is blue; the rest are purple.
The minimum time is 127 utilizing the path 1-2-4.
Initially, the light at junction 1 is blue. Since the light at junction 2 is purple, vehicle waits at junction 1 for 2 seconds then travels 4 seconds to junction 2.
At time 6, the light at junction 2 switches to blue whereas the light at junction 4 has 32 more seconds to switch to blue. However, after 32 seconds, the light at junction 2 switches to purple and the light at junction 4 switches to blue at the same time. So the vehicle needs to wait 13 seconds more for junction 2 to switch to blue then the lights have the same color and vehicle travels 76 seconds to the destination junction 4.
The total time is 2+4+32+13+76=127 seconds.
Below is a more graphical presentation of this travel plan:
1 1 1 1 1 1
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 0 0 1 1 2 2
0....5....0....5....0....5....0....5....0....5....0....5....0....5....0....5....0....5....0....5....0....5....0....5....0....5..
--------------------------------------------------------------------------------------------------------------------------------
J1 BBBPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPBBBBBBBBBBBBBBBBPPPPPPPPPP
J2 PPPPPPBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBPPPPPPPPPPPPPBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBPPPPPPPPPPPPPBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB
J3 PPPBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBPPPPBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB
J4 PPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB
FJ 1..>>>2............................................>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>4
输入格式
* Line 1: Two space-separated integers: S and D
* Line 2: Two space-separated integers: N and M
* Lines 3..N+2: Line i+2 line describes junction i with a character and three integers (all separated by a single space): C_i, R_i, DB_i, and DP_i
* Lines N+3..N+M+2: Line N+2+k describes road k with three integers: i, j, and T_ij
输出格式
* Line 1: One integer: the time taken by a minimum-time path from the source junction to the destination junction. If there is no path, output 0.
样例 #1
样例输入 #1
1 4
4 5
B 2 16 99
P 6 32 13
P 2 87 4
P 38 96 49
1 2 4
1 3 40
2 3 75
2 4 76
3 4 77
样例输出 #1
127
思路
考场上就想到了 \(SPFA\) ，但是不会处理颜色。
假设现在在 点 \(x\) ， 现在时间是 \(now\) ，现在判断是否松弛 \(y\)
如果 现在颜色相同，则直接松弛。
否则暴力把 \({x , now + 1}\) 加入队列
**记得每次从队列中取出数时要判断一下 \(now > inf \to continue\) **
下面是判断点 \(x\) ，\(y\) 时刻颜色的方法
首先 \(y < r_x \to c_x\)
否则
判断一下初始颜色
\(B\) 是 \(0\) ， \(P\) 是 \(1\)
颜色是 \(P\) 的话应满足
\(c_x == 0 \and (y - R_x) \mod (P_x + B_x) < P_x\) 或者 \(c_x == 1 \and (y - R_x) \mod (P_x +B_x) >= B_x\)
同理易得其他情况 ， 具体可以感性理解一下代码
code
#include <bits/stdc++.h>
#define LL long long
#define fu(x , y , z) for(int x = y ; x <= z ; x ++)
using namespace std;
const int inf = 1e9 + 5;
const int N = 305 , M = 100005;
int dis[N] , hd[N] , cnt , st , ed , n , m , a[N] , b[N] , p[N] , vis[N][M] , flg[N];
char c;
struct node {
int id , d;
};
queue<node> q;
struct E {
int to , nt;
LL w;
} e[M << 1];
void add (int x , int y , LL z) { e[++cnt].to = y , e[cnt].w = z , e[cnt].nt = hd[x] , hd[x] = cnt; }
int gc (int x , int t) {
if (t < a[x]) return flg[x];
int xx = (t - a[x]) % (b[x] + p[x]);
if (!flg[x])
return xx < p[x];
else
return xx >= b[x];
}
void Spfa () {
int y;
node x;
fu (i , 1 , n) dis[i] = inf;
q.push ((node){st , 0});
vis[st][0] = 1 , dis[st] = 0;
while (!q.empty()) {
x = q.front ();
q.pop ();
vis[x.id][x.d] = 0;
if (x.d >= M) continue;
for (int i = hd[x.id] ; i ; i = e[i].nt) {
y = e[i].to;
if (x.d + e[i].w < dis[y]) {
node xx;
if (gc (x.id , x.d) == gc (y , x.d)) {
dis[y] = x.d + e[i].w;
xx = (node){y , dis[y]};
}
else xx.id = x.id , xx.d = x.d + 1;
if (!vis[xx.id][xx.d]) {
vis[xx.id][xx.d] = 1;
q.push ((node){xx.id , xx.d});
}
}
}
}
}
int main () {
scanf ("%d%d" , &st , &ed);
scanf ("%d%d" , &n , &m);
fu (i , 1 , n) {
c = getchar ();
while (c != 'B' && c != 'P') c = getchar ();
flg[i] = (c == 'P');
scanf ("%d%d%d" , &a[i] , &b[i] , &p[i]);
}
int u , v;
LL w;
fu (i , 1 , m) {
scanf ("%d%d%lld" , &u , &v , &w);
add (u , v , w) , add (v , u , w);
}
Spfa();
if (dis[ed] >= inf) puts ("0");
else printf ("%d" , dis[ed]);
return 0;
}