P1075 星门待群钥官方题解

Gioush OJ · 星门待群钥 · 2026/09/07 00:00

【部分分：测试点 1∼31\sim 31∼3】

原题为 P2446 [SDOI2010] 大陆争霸。
对每个区域 $i$ ，分别维护沿航路到达星门前的最早时刻 $r_i$ ，以及所有前置区域完成的最晚时刻 $p_i$ 。
当全部前置区域都已经完成时，区域 $i$ 真正能够进入的时刻为

t_i=\max(r_i,p_i).

每次线性扫描所有尚未进入、前置条件已经满足的区域，选择 $t_i$ 最小者进入，再更新航路与依赖。时间复杂度为 $\mathcal O(n^2+m+s)$ 。

【部分分：测试点 4∼74\sim 74∼7】

特殊性质保证 $s=0$ ，所有区域都没有前置条件。
此时 $p_i=0$ ，区域进入时刻只由航路抵达时刻决定，题目退化为非负边权有向图上的单源最短路。
从区域 $1$ 出发运行普通 Dijkstra 即可，时间复杂度为 $\mathcal O((n+m)\log n)$ 。
这一档说明完整问题仍以最短路为骨架，前置条件只改变一个区域何时能够被正式取出。

【部分分：测试点 8∼118\sim 118∼11】

航路与前置关系都从编号较小的区域指向编号较大的区域，因此计算区域 $i$ 时，所有可能影响它的区域都已经计算完毕。
道路抵达部分满足

r_i=\min_{u\to i}(t_u+w_{u,i}),

前置完成部分满足

p_i=\max_{u\in\operatorname{pre}_i}t_u.

于是按照编号从小到大计算

t_i=\max(r_i,p_i)

即可。时间复杂度为 $\mathcal O(n+m+s)$ 。

【部分分：测试点 12∼1512\sim 1512∼15】

回到一般图。对每个区域 $i$ 再维护未完成前置条件的数量 $c_i$ 。
只有当 $c_i=0$ 且 $r_i$ 有限时，区域 $i$ 才成为候选区域，其候选时刻为 $\max(r_i,p_i)$ 。
每次线性扫描所有候选区域，取候选时刻最小者。进入后同时松弛出航路，并通知所有把它作为前置条件的区域。
这已经是完整算法，只是尚未使用堆。时间复杂度为 $\mathcal O(n^2+m+s)$ 。

【正解】

对区域 $i$ 维护三项信息：
$r_i$ ：已经完成的区域沿航路抵达 $i$ 的最早时刻。
$p_i$ ：已经完成的前置区域中，完成时刻的最大值。
$c_i$ ：尚未完成的前置区域数量。
初始时 $r_1=0$ ，其余 $r_i=+\infty$ 。所有 $p_i=0$ ， $c_i$ 等于输入给出的前置数量。
当 $c_i=0$ 且 $r_i<+\infty$ 时，把

(\max(r_i,p_i),i)

放入小根堆。

从堆中取出候选时刻最小的区域 $u$ 。若该记录已经过期，或者 $u$ 已经进入，直接丢弃。
否则令

t_u=\max(r_u,p_u),

并确定区域 $u$ 的最早进入时刻。

对每条航路 $u\to v$ ，执行

r_v\gets\min(r_v,t_u+w_{u,v}).

若此时 $c_v=0$ ，就把新的候选时刻放入堆。

对每个把 $u$ 作为前置区域的 $v$ ，执行

p_v\gets\max(p_v,t_u),\qquad c_v\gets c_v-1.

当 $c_v$ 第一次变为 $0$ 时，全部前置区域已经完成。若 $r_v$ 有限，就把

(\max(r_v,p_v),v)

放入堆。

航路更新可能多次改善 $r_v$ ，所以堆中允许保留旧记录。取出时比较当前值即可忽略过期记录。
证明仍然沿用 Dijkstra 的贪心顺序。设当前堆中最小候选时刻为 $T$ ，对应区域 $u$ 。
任何尚未进入的区域，其真正进入时刻都不小于当前候选时刻。若一条尚未处理的路径将来抵达 $u$ ，它必须先经过某个尚未进入的区域，再经过非负边权航路，因此抵达时刻不可能小于 $T$ 。
$u$ 的全部前置区域已经完成， $p_u$ 也不会再改变。故 $\max(r_u,p_u)=T$ 已经是最终答案，可以安全确定。
归纳处理所有区域，算法正确。
每条航路只在起点进入时松弛一次，每条前置关系只在前置区域进入时处理一次。
每次有效更新至多向堆中加入一条记录，堆规模为 $\mathcal O(n+m+s)$ 。
时间复杂度为

\mathcal O((n+m+s)\log n),

空间复杂度为 $\mathcal O(n+m+s)$ 。

关键始终是区分“信号已经抵达星门”和“星门已经允许进入”，两项时间分别取最小值与最大值，最后再取较大者。

【参考代码】

1/*2Author:Ehundategh3Date:2026/8/264Name:gateway.cpp5You steal,I kill.6*/7#include <queue>8#include <vector>9#include <cstdio>10#include <cstring>11#include <algorithm>12#define MAXN 20001013#define MAXM 50001014using namespace std;15 16const long long INF=0x3f3f3f3f3f3f3f3fll;17int T,n,m,Head[MAXN],NeedHead[MAXN],Deg[MAXN],Total,NeedTotal;18long long Road[MAXN],Pre[MAXN],Ans[MAXN];19bool Visited[MAXN];20 21struct edge{22    int Ed,Next,Value;23}Edge[MAXM],Need[MAXM];24 25void Edge_Add(int St,int Ed,int Value){Edge[++Total]={Ed,Head[St],Value};Head[St]=Total;}26void Need_Add(int St,int Ed){Need[++NeedTotal]={Ed,NeedHead[St],0};NeedHead[St]=NeedTotal;}27 28priority_queue<pair<long long,int>,vector<pair<long long,int> >,greater<pair<long long,int> > > Q;29 30void Push(int Now){31    if(!Deg[Now]&&Road[Now]!=INF) Q.emplace(max(Road[Now],Pre[Now]),Now);32}33 34void Solve(){35    int In1,In2,In3,k;36    scanf("%d%d",&n,&m);37    Total=NeedTotal=0;38    memset(Head,0,sizeof(Head));39    memset(NeedHead,0,sizeof(NeedHead));40    memset(Deg,0,sizeof(Deg));41    memset(Pre,0,sizeof(Pre));42    memset(Ans,0,sizeof(Ans));43    memset(Visited,0,sizeof(Visited));44    memset(Road,0x3f,sizeof(Road));45    while(!Q.empty()) Q.pop();46    for(int i=1;i<=m;i++){47        scanf("%d%d%d",&In1,&In2,&In3);48        Edge_Add(In1,In2,In3);49    }50    for(int i=1;i<=n;i++){51        scanf("%d",&k);Deg[i]=k;52        while(k-->0){scanf("%d",&In1);Need_Add(In1,i);}53    }54    Road[1]=0;Push(1);55    while(!Q.empty()){56        long long Value=Q.top().first;57        int Now=Q.top().second;Q.pop();58        if(Visited[Now]||Value!=max(Road[Now],Pre[Now])) continue;59        Visited[Now]=true;Ans[Now]=Value;60        for(int i=Head[Now];i;i=Edge[i].Next){61            int To=Edge[i].Ed;62            if(Road[To]>Value+Edge[i].Value){63                Road[To]=Value+Edge[i].Value;64                Push(To);65            }66        }67        for(int i=NeedHead[Now];i;i=Need[i].Next){68            int To=Need[i].Ed;69            Pre[To]=max(Pre[To],Value);70            Deg[To]--;71            Push(To);72        }73    }74    for(int i=1;i<=n;i++) printf("%lld%c",Ans[i],i==n?'\n':' ');75}76 77int main(){78    int c;79    scanf("%d%d",&c,&T);80    while(T-->0) Solve();81    return 0;82}