题目链接：
https://cn.vjudge.net/problem/SGU-103#author=ECUST_FZL
题目大意：
Dingiville 城市的交通规则非常奇怪，城市公路通过路口相连，两个不同路口之间最多只有一条直达公路。公路的起止点不会是同一路口。在任意一条公路上顺不同方向走所需 时间相同。每一个路口都有交通灯，这些交通灯在某一时刻要么是蓝色，要么是紫色。同一个灯上2个颜色的维持时间受到定期调控，总是蓝色持续一段时间，紫色 持续一段时间。交通规则规定两个路口可以通车仅当公路两边交通灯的颜色相同（也就是说只要你在A城市看见A与B的交通灯颜色相同，那么你就可以走上A-B 这条路并到达B点）。交通工具可以在路口等候。现在你有这个城市的地图，包含：
• 通过所有公路需要的时间(整数)
• 每个路口交通灯两种颜色的持续时间(整数)
• 每个路口交通灯的初始颜色以及初始颜色的持续时间(整数).
你的任务是找到一条从起点到终点的最快路径，当有多条这样的路径存在时，你只需输出任意一条即可。
解题思路：
可以用SPFA求解最短路，只是松弛的时候，计算两点的路径的时候需要计算一下。
只有u点的颜色和v点的颜色是一致的时候才可以从u到v，可以写出一个函数计算某时刻某个点的颜色，对于u v路径，可以枚举在dis[u] - dis[u] + 300内的所有时间直到两点颜色相同。这是由于周期最多为200，在一个半周期内没有解的话就无解了。
#include<bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = ;
struct Edge
{
int u, v, w;
Edge(){}
Edge(int u, int v, int w):u(u), v(v), w(w){}
};
vector<Edge>edges;//存每一条边
vector<int>Map[maxn];//存i相连的边的下标
void addedge(int u, int v, int w)
{
edges.push_back(Edge(u, v, w));
int m = edges.size();
Map[u].push_back(m - );
edges.push_back(Edge(v, u, w));
m = edges.size();
Map[v].push_back(m - );
} struct node
{
bool color;//color = 0为blue color = 1为purple
int init, tb, tp, tsum;
}a[maxn]; int color(int u, int time)//计算time时候 u点的颜色
{
time = (time - a[u].init + a[u].tsum) % a[u].tsum;
if(a[u].color)return time < a[u].tb ? : ;//最初为紫色的时候
else return time < a[u].tp ? : ;//最初为蓝色的时候
}
int Time(int u, int v, int now)//返回从u到v可以开始走的时间
{
for(int i = now; i <= now + ; i++)
if(color(u, i) == color(v, i))return i;
return INF;
} bool vis[maxn];
int d[maxn], path[maxn];
int n, m;
int SPFA(int s, int t)
{
memset(vis, , sizeof(vis));
memset(path, -, sizeof(path));
for(int i = ; i <= n; i++)d[i] = INF;
d[s] = ;
vis[s] = ;
queue<int>q;
q.push(s);
while(!q.empty())
{
int u = q.front();
q.pop();
vis[u] = ;
for(int i = ; i < Map[u].size(); i++)
{
Edge& e = edges[Map[u][i]];
int v = e.v;
int w = Time(u, v, d[u]) + e.w;//这是u到v的时间
if(d[v] > w)
{
d[v] = w;
path[v] = Map[u][i];
if(!vis[v])
{
q.push(v);
vis[v] = ;
}
} }
}
return d[t];
}
void Print(int s, int t)
{
stack<int>q;
int x = t;
while(path[x] != -)
{
q.push(x);
x = edges[path[x]].u;
}
printf("%d", s);
while(!q.empty())
{
printf(" %d", q.top());
q.pop();
}
puts("");
}
int main()
{
int s, t;
char c[];
scanf("%d%d", &s, &t);
scanf("%d%d", &n, &m);
for(int i = ; i <= n; i++)
{
scanf("%s%d%d%d", c, &a[i].init, &a[i].tb, &a[i].tp);
a[i].tsum = a[i].tb + a[i].tp;
a[i].color = c[] == 'P';
}
int u, v, w;
while(m--)
{
scanf("%d%d%d", &u, &v, &w);
addedge(u, v, w);
}
int ans = SPFA(s, t);
if(ans >= INF)
{
printf("0\n");
}
else
{
printf("%d\n", ans);
Print(s, t);
}
return ;
}