Wannafly挑战赛2_D Delete
Problem :
给定一张n个点，m条边的带权有向无环图，同时给定起点S和终点T，一共有q个询问，每次询问删掉某个点和所有与它相连的边之后S到T的最短路，询问之间互相独立(即删除操作在询问结束之后会立即撤销)，如果删了那个点后不存在S到T的最短路，则输出-1。
n,q <= 10^5
Solution :
注意到题中所给的是DAG，首先可以找出图中结点的拓扑序。对于删除掉某个点之后，若仍存在一条从S到T的最短路，那么对应到拓扑序中，必然有一条边跨过了该点(即这条边的两个端点的拓扑序在这个点的两边)。故对于每条边(u, v, w)， 对拓扑序(a[u], a[v])中的点提供了一条长度为ds[u]+dt[v]+w的最短路，用线段树来维护最小值。
注意特判若u->v不可能经过这个点，那么直接输出最短路。
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
const long long INF = 1ll << 60;
const int N = 1e5 + 8;
struct edge
{
int v, w;
edge(int v = 0, int w = 0):v(v),w(w){}
};
vector <edge> vec[N], vec2[N];
long long ds[N], dt[N];
int a[N], deg[N];
int n, m, S, T;
void init()
{
cin >> n >> m >> S >> T;
for (int i = 1; i <= n; ++i) vec[i].clear(), vec2[i].clear();
for (int i = 1; i <= m; ++i)
{
int u, v, w; cin >> u >> v >> w;
vec[u].push_back(edge(v, w));
vec2[v].push_back(edge(u, w));
deg[v]++;
}
}
void getDag()
{
static queue <int> Q;
int tot = 0;
for (int i = 1; i <= n; ++i)
{
if (deg[i] == 0)
{
a[i] = ++tot;
Q.push(i);
}
}
while (!Q.empty())
{
int u = Q.front(); Q.pop();
for (auto p : vec[u])
{
deg[p.v]--;
if (deg[p.v] == 0)
{
a[p.v] = ++tot;
Q.push(p.v);
}
}
}
}
struct node
{
int u;
long long w;
bool operator < (const node &b) const
{
return w > b.w;
}
};
void Dijkstra(int S, long long dis[], vector <edge> vec[])
{
static priority_queue<node> Q;
static bool vis[N];
for (int i = 1; i <= n; ++i) dis[i] = INF, vis[i] = 0;
Q.push((node){S, 0});
dis[S] = 0;
while (!Q.empty())
{
int u = Q.top().u; Q.pop();
if (vis[u]) continue;
vis[u] = 1;
for (auto p : vec[u])
if (dis[u] + p.w < dis[p.v])
{
dis[p.v] = dis[u] + p.w;
Q.push((node{p.v, dis[p.v]}));
}
}
}
class SegmentTree
{
public:
long long tag[N << 2];
void build(int l, int r, int rt)
{
tag[rt] = INF;
if (l == r) return;
int m = l + r >> 1;
build(l, m, rt << 1);
build(m + 1, r, rt << 1 | 1);
}
void update(int L, int R, long long val, int l, int r, int rt)
{
// if (l == 1 && r == n) cout << L << " " << R << " " << val << endl;
if (L <= l && r <= R)
{
tag[rt] = min(tag[rt], val);
return;
}
int m = l + r >> 1;
if (L <= m) update(L, R, val, l, m, rt << 1);
if (m < R) update(L, R, val, m + 1, r, rt << 1 | 1);
}
void query(int x, int l, int r, int rt, long long &ans)
{
ans = min(ans, tag[rt]);
if (l == r) return;
int m = l + r >> 1;
if (x <= m) query(x, l, m, rt << 1, ans);
else query(x, m + 1, r, rt << 1 | 1, ans);
}
}ST;
void buildSeg()
{
ST.build(1, n, 1);
for (int u = 1; u <= n; ++u)
for (auto p : vec[u])
if (a[u] + 1 < a[p.v] && ds[u] != INF && dt[p.v] != INF)
{
// cout << u << " " << p.v << " " << a[u] << " " << a[p.v] << endl;
ST.update(a[u] + 1, a[p.v] - 1, ds[u] + dt[p.v] + p.w, 1, n, 1);
}
}
void solve()
{
int Q; cin >> Q;
for (; Q; --Q)
{
int u; cin >> u;
long long ans = INF;
if (ds[u] == INF || dt[u] == INF)
{
cout << dt[S] << endl;
continue;
}
ST.query(a[u], 1, n, 1, ans);
if (ans == INF) cout << -1 << endl; else cout << ans << endl;
}
}
int main()
{
cin.sync_with_stdio(0);
init();
getDag();
Dijkstra(S, ds, vec);
Dijkstra(T, dt, vec2);
buildSeg();
solve();
}