题目描述

和$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_{i,j}$

输出格式

一个整数代表从$S$到$D$最少消耗的时间, 如果$S$、$D$不连通,输出$0$。

样例输入

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

样例输出

127

菜鸡的咆哮

一道数据范围很小的最短路问题,但是不能直接松弛了。

想要从$i$到$j$只有在$i$和$j$的信号灯颜色相同的时候才可以走

于是可以考虑将$SPFA$魔改一发+暴力等待每条边两端点同色水过。

在$SPFA$中,我们用队列来储存结构体$node$。

$node.id$表示点的编号,$node.d$表示所用的时间。

不妨设我们在第$now$个单位的时间到了点$x$,可以通过一条边花费$w$单位个时间到达点$y$:

若$now+w<dist[y]$则表示经过这条边可以在更早的时间到达$y$。

如果此时$x$和$y$处的信号灯是一个颜色,直接更新。

反之我们暴力地等待$1$个单位的时间,$inqueue$判断后看是否将$(node)${$x,now+1$}入队。

(这里可以计算需要多久同色,但数据范围太小了$QwQ$)(能水则水我真是太菜了)

【注意】

①如何判断第$now$个单位时间信号灯的颜色?

​ $c[i]$为初始颜色,$r[i]$为初始颜色剩余时间,$p_1[i],p_2[i]$分别为两种颜色持续时间。

​ Ⅰ 如果$now<r[i]$ 一次都没变 返回$c[i]$

​ Ⅱ进行$n$轮变化后还剩下$xx=(now-r[x])\%(p1[x]+p2[x])$ 个单位的时间。

​ 讨论初始颜色的另一颜色的周期与$xx$的大小确定当前颜色。

②如果在变幻灯的那一秒,考虑的是变幻后的颜色。(如果不注意会$WA$前两个点)

③如果$now$很大了就$continue$了,有可能两点的灯根本不可能同色。

(这里有点玄学,具体多大有待考究$QwQ$,但是不考虑会在第$9$个点$TLE$)

考场上瞎搞的,肯定有许多可以优化的地方,大佬们轻喷$QAQ$

代码

#include<bits/stdc++.h>
#define maxn 50005
using namespace std;
int s,e,n,m;
int c[maxn],r[maxn];
int p1[maxn],p2[maxn];
struct data{
    int to;
    int p;
    int nextt;
}line[maxn];
int tail;
int first[maxn];
void add(int x,int y,int w){
    tail++;
    line[tail].to=y;
    line[tail].p=w;
    line[tail].nextt=first[x];
    first[x]=tail;
}
int color(int now,int x){
    if(now<r[x]) return c[x];
    int xx=(now-r[x])%(p1[x]+p2[x]);
       if(c[x]==1){
            if(xx-p2[x]>=0) return 1;
            return 2;
       }
       else{
               if(xx-p1[x]>=0) return 2;
               return 1;
       }
}
struct node{
    int id,d;
};
int dist[maxn];
int inqueue[305][100005];
queue<node> q;
void SPFA(){
    memset(dist,0x3f,sizeof(dist));
    dist[s]=0;
    q.push((node){s,0});
    inqueue[s][0]=1;
    while(!q.empty()){
        node t=q.front();q.pop();
        int x=t.id;
        int now=t.d;
        inqueue[x][now]=0;
        if(now>100005) continue; 
        for(int i=first[x];i;i=line[i].nextt){
            int y=line[i].to;
            int w=line[i].p;
            if(now+w<dist[y]){
                node xx;
                if(color(now,x)==color(now,y)){
                    dist[y]=now+w;
                    xx.id=y;xx.d=dist[y];    
                }
                else xx.id=x,xx.d=now+1;
                if(!inqueue[xx.id][xx.d]){
                    q.push(xx);
                    inqueue[xx.id][xx.d]=1;
                }
            }
        }
    }
}
int main(){
    scanf("%d%d%d%d",&s,&e,&n,&m);
    int a,b,q;char xx;
    for(int i=1;i<=n;i++){
        cin>>xx;
        c[i]=(xx=='B')?1:2;
        scanf("%d%d%d",&r[i],&p1[i],&p2[i]);
    }
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&a,&b,&q);
        add(a,b,q);add(b,a,q);
    }
    SPFA();
    if(dist[e]>200000000) puts("0");
    else printf("%d\n",dist[e]);
    return 0;
}