USACO23FEB S T3 题解

H_Kaguya · 2023-03-02 07:24:19 · 题解

赛时想了想感觉没啥思路，结果最后写了一个麻烦的做法。

首先把下飞机之后的等待时间算到边权上，这就是一个普通的最短路了。
发现负边权最短路本身没啥好性质，所以考虑出发和到达时间固定这一点。

套路拆点。对于每个点，可能的到达 / 出发时间是有限的，我们就拆出来若干个点。
显然，可以在一个机场里等着，所以一个机场拆出来的点按时间顺序连一个链。
至于航班，就在相应的时间点之间连边。
这样，我们就把最短路问题转化成了连通性问题。跑一遍 BFS 即可。

由于边数是 O(n) 级别的，所以最后出来的总点数也是 O(n) 的。
由于需要按时间排序，所以总复杂度 O(n\log n)。
当然，可以把所有点放在一起基数排序，并且用单调指针代替二分查找来做到线性。实现就算了。

放上蒟蒻的赛时代码。

#include <algorithm>
#include <stdio.h>
#include <vector>
using namespace std;
#define sz 200005
struct site
{
    int st, stim, ed, etim;
};
site dld[sz];
int n, m, top;
int wei[sz];
bool vis[sz << 1 | 1];
vector<int> tim[sz], ber[sz], fsl[sz << 1 | 1];
int read();
int haf(int, int);
void dfs(int);
int main()
{
    int x, y;
    n = read(); m = read();
    for (int i = 1; i <= m; ++i)
    {
        dld[i].st = read();
        dld[i].stim = read();
        dld[i].ed = read();
        dld[i].etim = read();
    }
    for (int i = 1; i <= n; ++i)
        wei[i] = read();
    for (int i = 1; i <= m; ++i)
    {
        tim[dld[i].st].emplace_back(dld[i].stim);
        tim[dld[i].ed].emplace_back(dld[i].etim + wei[dld[i].ed]);
    }
    for (int i = 1; i <= n; ++i)
        if (tim[i].size())
        {
            sort(tim[i].begin(), tim[i].end());
            x = 0;
            for (int j = 1; j < tim[i].size(); ++j)
                if (tim[i][j] != tim[i][x])
                    tim[i][++x] = tim[i][j];
            tim[i].resize(x + 1);
            for (int j = 0; j <= x; ++j)
                ber[i].emplace_back(++top);
            for (int j = 1; j <= x; ++j)
                fsl[ber[i][j - 1]].emplace_back(ber[i][j]);
        }
    for (int i = 1; i <= m; ++i)
    {
        x = haf(dld[i].st, dld[i].stim);
        y = haf(dld[i].ed, dld[i].etim + wei[dld[i].ed]);
        fsl[x].emplace_back(y);
    }
    if (ber[1].size())
        dfs(1);
    puts("0");
    for (int i = 2; i <= n; ++i)
    {
        x = 1;
        for (int j = 0; j < ber[i].size(); ++j)
            if (vis[ber[i][j]])
            {
                printf ("%d\n", tim[i][j] - wei[i]);
                x = 0; break;
            }
        if (x)
            puts("-1");
    }
    return 0;
}

int read()
{
    int x = 0;
    char c = getchar();
    while (c < '0') c = getchar();
    do {
        x = x * 10 + (c & 15);
        c = getchar();
    }while (c >= '0');
    return x;
}

int haf(int a, int b)
{
    int lf = 0, rt = tim[a].size(), mid;
    while (rt > lf + 1)
    {
        mid = lf + rt >> 1;
        if (tim[a][mid] <= b)
            lf = mid;
        else
            rt = mid;
    }
    return ber[a][lf];
}

void dfs(int a)
{
    vis[a] = true;
    for (int i : fsl[a])
        if (!vis[i])
            dfs(i);
}