知識點：最短路
原題面： Luogu
扯
講課的時候随便找的題，一眼了，瞎寫了一下挂了。
看了題解，學習了。
題意簡述
給定一 \(n\) 個點，\(m\) 條邊的有向圖，邊有邊權。
有無限個人同時從 \(1\) 号節點出發，可按照任意路徑行走。
對于每一個節點，存在一些限制節點，當所有的限制節點都有人進入後，人才可進入該節點。
求在上述限制下，\(1\rightarrow n\) 的最短路。
\(1\le n\le 3\times 10^3\)，\(1\le m\le 7\times 10^4\)。
分析題意
帶有限制的最短路問題。
設 \(arrive_i\) 表示在滿足上述限制下，\(1\rightarrow i\) 的最短路。
\(in_i\) 表示節點 \(i\) 的所有限制被摧毀的最短時間。
\(dis_i\) 表示進入 \(i\) 的實際時間。
則顯然有：
\[in_i = \max\limits_{j \text{為} i \text{的限制節點}}{dis_j}_{}
\]
\[dis_i = \max{(arrive_i, in_i)}
答案即為 \(dis_n\)。
發現一個點能用于更新其他點，前提是該點能被進入，即所有該點的限制節點均可到達，且該點的所有前驅均可到達。
考慮使用 Dijkstra 求得上述 \(arrive\) 與 \(in\)。
每次找到還未被标記的，所有限制節點均已被标記的，\(dis\) 最小的節點，将其标記。
可以證明不存在其他節點可以疏導該節點，則用它來疏導與其相連的節點的 \(arrive\)，并更新以其為限制節點的節點的 \(in\)。
資料範圍較小，不進行優化也可過，代碼中使用了堆優化。
以下是一個容易想到，但是錯誤的拓撲排序做法。
先跑出以 \(1\) 為起點的最短路。
由于保證有解，發現節點的限制關系，形成了一張 DAG。
對這張 DAG 進行拓撲排序，将 沒有入度的點 的 \(dis_i\) 指派為最短路，之後使用上述轉移進行更新。
獲得了 10 分的好成績，以下是一組 hack 資料：
4 3
1 2 1
1 3 5
2 4 1
0
0
1 2
0
如果按上述方法進行，會輸出 2，原因是終點并沒有被直接限制，在 DAG 中沒有入度，會被直接指派。
爆零小技巧
多造資料卡自己一定沒有錯。
代碼實作
//知識點：最短路
/*
By:Luckyblock
*/
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#define ll long long
#define pr std::pair
#define mp std::make_pair
const int kMaxn = 3e3 + 10;
const int kMaxm = 1e5 + 10;
const ll kInf = 1e15 + 2077;
//=============================================================
int n, m, s;
int edge_num, head[kMaxn], v[kMaxm], w[kMaxm], ne[kMaxm];
ll arrive[kMaxn], in[kMaxn], dis[kMaxn];
bool vis[kMaxn];
int into[kMaxn];
std :: vector <int> pro[kMaxn];
//=============================================================
inline int read() {
int f = 1, w = 0;
char ch = getchar();
for (; !isdigit(ch); ch = getchar())
if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
void Chkmax(ll &fir_, ll sec_) {
if (sec_ > fir_) fir_ = sec_;
}
void Chkmin(int &fir_, int sec_) {
if (sec_ < fir_) fir_ = sec_;
}
void AddEdge(int u_, int v_, int w_) {
v[++ edge_num] = v_, w[edge_num] = w_;
ne[edge_num] = head[u_], head[u_] = edge_num;
}
void Dijkstra(int s_) {
std :: priority_queue <pr <ll, int> > q;
memset(vis, false, sizeof (vis));
memset(arrive, 63, sizeof (arrive));
memset(arrive, 63, sizeof (dis));
arrive[s_] = 0;
dis[s_] = 0;
q.push(mp(0, s_));
while (! q.empty()) {
int u_ = q.top().second;
q.pop();
if (vis[u_]) continue ;
vis[u_] = true;
for (int i = head[u_]; i; i = ne[i]) {
int v_ = v[i], w_ = w[i];
if (arrive[v_] > dis[u_] + 1ll * w_) {
arrive[v_] = dis[u_] + 1ll * w_;
dis[v_] = std :: max(arrive[v_], in[v_]);
if (! into[v_]) q.push(mp(- dis[v_], v_));
}
}
for (int j = 0, size = pro[u_].size(); j < size; ++ j) {
int v_ = pro[u_][j];
into[v_] --;
in[v_] = std :: max(in[v_], dis[u_]);
dis[v_] = std :: max(arrive[v_], in[v_]);
if (! into[v_]) {
q.push(mp(- dis[v_], v_));
}
}
}
}
//=============================================================
int main() {
n = read(), m = read();
for (int i = 1; i <= m; ++ i) {
int u_ = read(), v_ = read(), w_ = read();
AddEdge(u_, v_, w_);
}
for (int i = 1; i <= n; ++ i) {
int l = read();
for (int j = 1; j <= l; ++ j) {
int u_ = read();
pro[u_].push_back(i);
into[i] ++;
}
}
Dijkstra(1);
printf("%lld\n", dis[n]);
return 0;
}
作者@Luckyblock，轉載請聲明出處。