洛谷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;
}