题意很清晰，直接跑 SPFA 求最短路。
只是我们在松弛操作时，需要注意从 \(u\) 是否可以到达 \(v\)。
怎么判断呢？
请移步下面三个部分。
Part 1
先解释一下，下面点 \(i\) 的信息分别为以下变量：
color表示颜色，1表示蓝色，0表示紫色num表示初始状态持续时间t1表示蓝色状态持续时间t2表示紫色状态持续时间
我们写一个函数 getcolor(int i,int tim)，表示点 \(i\) 在 \(tim\) 时刻的下一个颜色状态是什么。
分一下情况：
- \(tim<num[i]\)，直接返回
color[i]^1。 - \(tim\geq num[i]\)
- \(color[i]\) 为紫色
- \((tim-num[i])\mod \ (t1[i]+t2[i])<t1[i]\)，返回
color[i]。 - \((tim-num[i])\mod \ (t1[i]+t2[i])\geq t1[i]\)，返回
color[i]^1。
- \((tim-num[i])\mod \ (t1[i]+t2[i])<t1[i]\)，返回
- \(color[i]\) 为蓝色
- \((tim-num[i])\mod \ (t1[i]+t2[i])<t2[i]\)，返回
color[i]。 - \((tim-num[i])\mod \ (t1[i]+t2[i])\geq t2[i]\)，返回
color[i]^1。
- \((tim-num[i])\mod \ (t1[i]+t2[i])<t2[i]\)，返回
- \(color[i]\) 为紫色
code
bool getcolor(int i,int tim)
{
bool color=a[i].color^1;
if(tim<a[i].num)
return color;
tim-=a[i].num;
tim%=(a[i].t1+a[i].t2);
if(a[i].color==0)
{
if(tim<a[i].t1)
return color^1;
return color;
}
else
{
if(tim<a[i].t2)
return color^1;
return color;
}
}
Part 2
得到一个函数，仅仅只能求第 \(tim\) 时刻的下一个颜色状态是远远不够的。
我们还需要与这个函数类似功能的函数 gettim(int i,int tim)。
意义为：
得到一个值，这个值表示点 \(i\) 在 \(tim\) 时刻变成下一个状态还需要多少时间。
与上一 Part 类似的，可以分讨一下：
- \(tim<num[i]\)，直接返回
num[i]-tim。 - \(tim\geq num[i]\)
- \(color[i]\) 为紫色
- \((tim-num[i])\mod \ (t1[i]+t2[i])<t1[i]\)，返回
t1[i]-tim。 - \((tim-num[i])\mod \ (t1[i]+t2[i])\geq t1[i]\)，返回
t1[i]+t2[i]-tim。
- \((tim-num[i])\mod \ (t1[i]+t2[i])<t1[i]\)，返回
- \(color[i]\) 为蓝色
- \((tim-num[i])\mod \ (t1[i]+t2[i])<t2[i]\)，返回
t2[i]-tim。 - \((tim-num[i])\mod \ (t1[i]+t2[i])\geq t2[i]\)，返回
t1[i]+t2[i]-tim。
- \((tim-num[i])\mod \ (t1[i]+t2[i])<t2[i]\)，返回
- \(color[i]\) 为紫色
代码也很类似。
code
int gettim(int i,int tim)
{
if(tim<a[i].num)
return a[i].num-tim;
tim-=a[i].num;
tim%=(a[i].t1+a[i].t2);
if(a[i].color==0)
{
if(tim<a[i].t1)
return a[i].t1-tim;
return a[i].t1+a[i].t2-tim;
}
else
{
if(tim<a[i].t2)
return a[i].t2-tim;
return a[i].t1+a[i].t2-tim;
}
}
Part 3
得到了这两个函数，一切都变得简单多啦~
现在思考在松弛中面对 \(u\) 和 \(v\) 两个点时的情况。
先是用变量 cu 和 cv 分别表示 \(u\) 的下一个颜色与 \(v\) 的下一个颜色。
- 如果 \(cu=cv\)，直接松弛。
- 如果 \(cu\neq cv\)，多拿一个变量
tmp负责接下来记录要等待多少时间才能从 \(u\) 走到 \(v\)。
现在讨论 \(cu\neq cv\) 的情况。
先分别得到 \(u\) 和 \(v\) 变成下一个状态所需要的时间 tu 和 tv。
- 如果 \(tu=tv\)，则
tmp=min(tu,tv)。 - 如果 \(tu\neq tv\)，说明接下来要看周期性的颜色变换是否可以让 \(u\) 走到 \(v\)。
现在讨论周期性的颜色变换。
由于是周期性的，所以如果 \(u\) 注定永远走不到 \(v\)，说明它们的周期总是交叉相等。
什么意思呢？举个例子。
u: B 6 10 70
v: P 6 70 10
上面这两个点，总是同时变换状态，所以永远不能到达。所以我们判断周期是否交叉相等就可以筛掉无法到达的情况。直接 continue 松弛下一个 \(v'\)。
那接下来就注定可以到达，直接分讨一下就可以得到 tmp 了。
tmp 一出，有手就行。只需要在松弛的判断中加上一个 tmp 就好了。
代码
code
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN=400+5,MAXM=14000+5,INF=1e18;
int s,t;
int n,m;
int su,hd[MAXN],vl[MAXM<<1],lt[MAXM<<1],en[MAXM<<1];
int dis[MAXN];
bool vis[MAXN];
struct node
{
bool color;
int num,t1,t2;
}a[MAXN];
void add(int u,int v,int w)
{
en[++su]=v,vl[su]=w,lt[su]=hd[u],hd[u]=su;
}
bool getcolor(int i,int tim)
{
bool color=a[i].color^1;
if(tim<a[i].num)
return color;
tim-=a[i].num;
tim%=(a[i].t1+a[i].t2);
if(a[i].color==0)
{
if(tim<a[i].t1)
return color^1;
return color;
}
else
{
if(tim<a[i].t2)
return color^1;
return color;
}
}
int gettim(int i,int tim)
{
if(tim<a[i].num)
return a[i].num-tim;
tim-=a[i].num;
tim%=(a[i].t1+a[i].t2);
if(a[i].color==0)
{
if(tim<a[i].t1)
return a[i].t1-tim;
return a[i].t1+a[i].t2-tim;
}
else
{
if(tim<a[i].t2)
return a[i].t2-tim;
return a[i].t1+a[i].t2-tim;
}
}
void SPFA()
{
for(int i=1;i<=n;i++) dis[i]=INF;
queue<int> q;
q.push(s);
vis[s]=1,dis[s]=0;
while(!q.empty())
{
int u=q.front();q.pop();
for(int i=hd[u];i;i=lt[i])
{
int v=en[i];
int tmp=0;
bool cu=getcolor(u,dis[u]);
bool cv=getcolor(v,dis[u]);
if(cu^cv)
{
int tu=gettim(u,dis[u]);
int tv=gettim(v,dis[u]); // simple turn once
if(tu==tv) // hard turn more
{
if(a[u].t2==a[v].t1&&a[u].t1==a[v].t2)
continue;
if(cu==0) // now u is purple
{
if(a[u].t2==a[v].t1)
tmp=a[u].t2+min(a[u].t1,a[v].t2);
else
tmp=min(a[u].t2,a[v].t1);
}
else // now u is blue
{
if(a[u].t1==a[v].t2)
tmp=a[u].t1+min(a[u].t2,a[v].t1);
else
tmp=min(a[u].t1,a[v].t2);
}
tmp+=tu;
}
else
tmp=min(tu,tv);
}
if(dis[v]>dis[u]+tmp+vl[i])
{
dis[v]=dis[u]+tmp+vl[i];
if(!vis[v])
vis[v]=1,q.push(v);
}
}
vis[u]=0;
}
}
signed main()
{
scanf("%lld%lld%lld%lld",&s,&t,&n,&m);
for(int i=1,num,t1,t2;i<=n;i++)
{
char ch;
scanf("%s%lld%lld%lld",&ch,&num,&t1,&t2);
a[i]={(ch=='B'),num,t1,t2};
}
for(int i=1,u,v,w;i<=m;i++)
{
scanf("%lld%lld%lld",&u,&v,&w);
add(u,v,w);
add(v,u,w);
}
SPFA();
if(dis[t]==INF)
dis[t]=0;
printf("%lld\n",dis[t]);
return 0;
}