Time limit per test: 0.25 second(s)
Memory limit: 4096 kilobytes
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.
Input
The first line contains two numbers: The id-number of the source junction and the id-number of the destination junction. The second line contains two numbers: N, M. The following N lines contain information on N junctions. The (i+2)’th line of the input file holds information about the junction i : Ci, riC, tiB, tiP where Ci is either B for blue or P for purple, indicating the initial color of the light at the junction i. Finally, the next M lines contain information on M roads. Each line is of the form: i, j, lij where i and j are the id-numbers of the junctions which are connected by this road. 2 ≤ N ≤ 300 where N is the number of junctions. The junctions are identified by integers 1 through N. These numbers are called id-numbers. 1 ≤ M ≤ 14000 where M is the number of roads. 1 ≤ lij ≤ 100 where lij is the time required to move from junction i to j using the road that connects i and j. 1 ≤ tiC ≤ 100 where tiC is the duration of the color c for the light at the junction i. The index c is either ‘B’ for blue or ‘P’ for purple. 1 ≤ riC ≤ tiC where riC is the remaining time for the initial color c at junction i.
Output
If a path exists:
The first line will contain the time taken by a minimum-time path from the source junction to the destination junction.
Second line will contain the list of junctions that construct the minimum-time path you have found. You have to write the junctions to the output file in the order of travelling. Therefore the first integer in this line must be the id-number of the source junction and the last one the id-number of the destination junction.
If a path does not exist:
A single line containing only the integer 0.
sample input
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
sample output
127
1 2 4
题意：
一张有向图，给出起点和终点。每个点有个交通灯，可能是蓝色或紫色（让我想到了SNH48 的SⅡ和NⅡ）。每个点的蓝色和紫色各有一个持续时间（每个点的交通灯数据不一定相同），并且有一个0时刻的初始颜色以及初始颜色剩余的持续时间（毛子干嘛非要把题目弄这么复杂）。每条道路有一个非负整数的长度。从一个节点到另一个节点，当且仅当这两个节点的交通灯颜色相同，也就是说如果到了一个节点，想要去另一个节点而那个节点和这个颜色不同，需要等待一定的时间。求起点到终点的最短路长度和路径上经过的节点，如不连通输出一个零。
题解：
很明显，这是一道最短路的问题，但是对于边权的计算很麻烦，所以这道题的重点不在于最短路，在于如何计算边的边权，对于边权的计算，我们可以通过当前的状态和路灯的周期性变化计算我们在此刻要等待的时间，同时要注意，如果连续两个周期都没有相同的时候，那么就说明这条边不可行，这一点是我从网上看来的，因为SGU的题虽然数据小，但是对于空间和时间的要求非常苛刻，所以要注意卡常技巧。
同时要注意空间大小，我就因为空间被卡了好几次。。。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int MAXN = 3050, MAXM = 30000;
const int INF = 0x3f3f3f3f;
int st, ed, n, m;
int oc[MAXN];
int rest[MAXN], tb[MAXN], tp[MAXN];
int d[MAXN], pre[MAXN];
int rou[MAXN], rn;
int fst[MAXM], nxt[MAXM], tot = 0;
bool used[MAXN];
struct qer
{
int from, to, cost;
}es[MAXM];
queue <int> q;
void build(int f, int t, int dd)
{
es[++tot] = (qer){f, t, dd};
nxt[tot] = fst[f];
fst[f] = tot;
}
inline int color (int u, int t)
{
if (t < rest[u])
return oc[u];
t = (t - rest[u]) % (tb[u] + tp[u]);
if (!oc[u])
return t < tp[u] ? 1 : 0;
return t < tb[u] ? 0 : 1;
}
inline int nxttm(int u, int t)
{
int t1;
if (t < rest[u])
t1 = rest[u];
else
{
t1 = (t - rest[u]) % (tb[u] + tp[u]);
if (!oc[u])
{
if (t1 < tp[u])
t1 = t + tp[u] - t1;
else
t1 -= tp[u], t1 = t + tb[u] - t1;
}
else
{
if (t1 < tb[u])
t1 = t + tb[u] - t1;
else
t1 -= tb[u], t1 = t + tp[u] - t1;
}
}
return t1;
}
bool relax(int u, int v, int dd)
{
if (d[v] < d[u])
return 0;
int c1 = color(u, d[u]), c2 = color(v, d[u]);
if (c1 == c2)
{
if (d[u] + dd < d[v])
{
d[v] = d[u] + dd;
return 1;
}
return 0;
}
else
{
int t1 = d[u], t2 = d[u], wit = -1, tt;
for (int i = 1; i < 4; i++)
{
t1 = nxttm(u, t1);
t2 = nxttm(v, t2);
if (t1 == t2)
continue;
tt = t1 < t2 ? t1 : t2;
if (color(u, tt) == color(v, tt))
{
wit = (t1 < t2 ? t1 : t2);
break;
}
}
if (wit == -1 || wit + dd >= d[v])
return 0;
d[v] = wit + dd;
return 1;
}
}
void spfa()
{
memset(d, 0x3f, sizeof(d));
q.push(st);
used[st] = 1;
d[st] = 0;
while (!q.empty())
{
int u = q.front();
q.pop();
used[u] = 0;
for (int i = fst[u]; i; i = nxt[i])
{
int v = es[i].to;
if (relax(u, v, es[i].cost))
{
pre[v] = u;
if (!used[v])
{
used[v] = 1;
q.push(v);
}
}
}
}
}
int main()
{
int a, b, c;
scanf("%d%d%d%d", &st, &ed, &n, &m);
if (st == ed)
{
printf("0\n%d\n", st);
return 0;
}
char str[5];
for (int i = 1; i <= n; i++)
{
scanf("%s%d%d%d", str, rest+i, tb+i, tp+i);
oc[i] = (str[0] == 'P');
}
for (int i = 1; i <= m; i++)
{
scanf("%d%d%d", &a, &b, &c);
build(a, b, c);
build(b, a, c);
}
spfa();
if (d[ed] >= INF)
{
puts("0");
return 0;
}
printf("%d\n", d[ed]);
a = ed;
do
{
rou[++rn] = a;
a = pre[a];
}
while (a);
for (int i = rn; i >= 1; i--)
{
printf("%d%c", rou[i], i == 1 ? '\n' :' ');
}
return 0;
}