[USACO JAN 2011]交通灯题解

题意很清晰，直接跑 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。
- $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。

code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


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。
- $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。

代码也很类似。
code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


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$，说明它们的周期总是交叉相等。

什么意思呢？举个例子。

1
2


u: B 6 10 70
v: P 6 70 10

上面这两个点，总是同时变换状态，所以永远不能到达。所以我们判断周期是否交叉相等就可以筛掉无法到达的情况。直接 continue 松弛下一个 $v’$。

那接下来就注定可以到达，直接分讨一下就可以得到 tmp 了。
tmp 一出，有手就行。只需要在松弛的判断中加上一个 tmp 就好了。

代码

code

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138


#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;
}