洛谷P10199 [湖北省选模拟 2024] 时与风 / wind 题解

题目链接：P10199 [湖北省选模拟 2024] 时与风 / wind

题意：

风带来故事的种子，时间使之神话。

你在 $N$ 个锚点间，沿着 $M$ 条有向航道，使用风之翼进行飞行。锚点依次编号为 $1,2,\cdots,N$，有向航道依次编号为 $1,2,\cdots,M$。第 $i$ 条航道的出发锚点为 $u_i$，到达锚点为 $v_i$。

由于巴巴斯托与时间存在神秘的联系，第 $i$ 条航道将在时刻 $O_i$ 开启，在时刻 $C_i$ 后关闭。也就是说，对于任意的 $O_i \le t \le C_i$，你可以在时刻 $t$ 由锚点 $u_i$ 进入航道 $i$。进入航道后，空间上，你将直接到达锚点 $v_i$，时间上，时间将等概率的变化为 $[L_i,R_i]$ 中的一个实数对应的时刻。注意到达一个锚点后，你必须在同一时刻立刻进入下一段航道，否则你必须在此结束飞行。

你将从锚点 $S$ 出发，尝试访问锚点 $i(1\le i\le N)$，你需要对于锚点 $i$ 确定一条路径 $E_1,E_2,E_3,\cdots,E_k$，其中 $E_x(1\le x\le k)$ 表示一条航道。要求 $E_1$ 从锚点 $S$ 出发，$E_k$ 到达锚点 $i$，且对于 $1\le j<k$，满足 $E_j$ 的到达锚点与 $E_{j+1}$ 的出发锚点相同。一条路径是稳定路径，当且仅当无论每次通过航道后时间如何变化，都可以走完整条路径。一条稳定路径的到达时间是通过路径前往锚点 $i$ 时，最晚的可能到达锚点 $i$ 的时刻。访问锚点 $i$ 的稳定到达时间 $T_i(i \neq S)$ 是所有到达 $i$ 的稳定路径中到达时间的最小值。你可以在任意非负时刻出发。如果不存在访问锚点 $i$ 的稳定路径或 $i=S$，则 $T_i=0$。

请你求出 $T_i(1\le i\le N)$ 的最大值。

输入格式：

输入共 $M+1$ 行。

输入的第一行为三个整数 $N,M,S$，分别表示锚点数、航道数和起点锚点。

接下来 $M$ 行，每行包含六个整数 $u_i,v_i,O_i,C_i,L_i,R_i$，描述了第 $i$ 条航道的有关信息，变量具体含义见题目描述部分。

输出格式：

输出一行一个整数，表示 $T_i$ 的最大值。

数据范围：

$1 \le N,M \le 5\times 10^5$，$1 \le O_i,L_i \le 20$，$1 \le O_i \le C_i \le 10^9$，$1 \le L_i \le R_i \le 10^9$，$1\le S \le N$。

一般题目中出现“实数内随机”都是吓人的，显然这道题也是这样的。

实际上我们只关心一条路径最早和最晚到的时刻，这决定了下一条边是否能发挥它的作用。

然而这道题并不适用最短路算法，因为我们对于两条路径含有不重合时间段的情况无法讨论其优先级。

显然这是一个二维偏序问题，我们需要固定其中的一维，同时算法也换成普通的 bfs。

可以发现，因为 $1\le O_i,L_i\le 20$ 所以我们可以用优先队列维护起始时刻 $1$ 到 $20$ 的每条边

对于每条路径，我们在小于等于其 $O_i$ 的每一个位置取出大于等于其 $R_i$ 的所有边

因为每个点的答案仅与更新它的边有关，即只有边能够更新答案，所以每条边至多产生 $1$ 的复杂度贡献

时间复杂度 $\mathcal{O}(V_Lm + m \log m)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
namespace FastIO
{
    #define gc() readchar()
    #define pc(a) putchar(a)
    #define SIZ (int)(1e6 + 15)
    char buf1[SIZ], *p1, *p2;
    char readchar()
    {
        if(p1 == p2){ p1 = buf1,p2 = buf1 + fread(buf1, 1, SIZ, stdin); }
        return p1 == p2? EOF : *p1++;
    }
    template<typename T>void read(T &k)
    {
        char ch = gc(); T x = 0, f = 1;
        while(!isdigit(ch)){ if(ch == '-'){ f = -1; }ch = gc(); }
        while(isdigit(ch)){ x = (x << 1) + (x << 3) + (ch ^ 48); ch = gc(); }
        k = x * f;
    }
    template<typename A, typename ...B>
        void read(A &x, B &...y) { return read(x), read(y...); }
    template<typename T>void write(T k)
    {
        if(k < 0){ k = -k; pc('-'); }
        static T stk[66]; T top = 0;
        do{ stk[top++] = k % 10, k /= 10; } while(k);
        while(top) { pc(stk[--top] + '0'); }
    }
}using namespace FastIO;
#define N ((int)(5e5 + 15))

int n,m,res,T[N];
struct node{ int v, a, b, c, d, id; };
bool operator<(node a, node b) { return a.b < b.b; }
vector<node> vec[N];
priority_queue<node> p[N][21];
queue<int> q; set<node> st[N];
void upd(int u, int x) { T[u] = (T[u] ? min(T[u], x) : x); }
void insert(int u, node x)
{
    for(int i = x.c; i; i--)
    {
        while(!p[u][i].empty() && p[u][i].top().b >= x.d)
        {
            auto tmp = p[u][i].top(); p[u][i].pop();
            q.push(tmp.v); st[u].insert(tmp); upd(tmp.v, tmp.d); 
        }
    }
}
void solve(int s)
{
    for(int i = 1; i <= n; i++)
        for(auto x : vec[i]) p[i][x.a].push(x);
    for(auto x : vec[s]) {
        upd(x.v, x.d); q.push(x.v); insert(x.v, x);
    }
    while(!q.empty())
    {
        int u = q.front(); q.pop();
        if(!T[u]) continue;
        for(auto x : st[u]) insert(x.v, x);
        st[u].clear();
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int s; read(n, m, s);
    for(int i = 1; i <= m; i++)
    {
        int u, v, a, b, c, d;
        read(u, v, a, b, c, d);
        vec[u].push_back({v, a, b, c, d, i});
    }
    solve(s);
    for(int i = 1; i <= n; i++) up(res, T[i]);
    write(res); pc('\n');
    return 0;
}