[Wannafly挑戰(zhàn)賽2D-Delete]最短路

題目描述

給定一張 n?個(gè)點(diǎn)，m?條邊的帶權(quán)有向無環(huán)圖，同時(shí)給定起點(diǎn) S?和終點(diǎn) T ，一共有 q 個(gè)詢問，每次詢問刪掉某個(gè)點(diǎn)和所有與它相連的邊之后 S?到 T?的最短路，詢問之間互相獨(dú)立(即刪除操作在詢問結(jié)束之后會(huì)立即撤銷)，如果刪了那個(gè)點(diǎn)后不存在 S?到 T?的最短路，則輸出 ?1?。點(diǎn)的編號(hào)為 1?到 n?。

輸入格式

第一行四個(gè)正整數(shù)表示 n,m,S,T ，意義如題所述。

接下來 m?行每行三個(gè)正整數(shù) x,y,z ，表示有一條?x 到 y?的有向邊，權(quán)值為 z 。

接下來一行一個(gè)正整數(shù) Q?表示詢問次數(shù)。

最后 Q?行每行一個(gè)正整數(shù) k?表示這次詢問要?jiǎng)h除點(diǎn) k??。

輸出格式

輸出 Q?行，每行一個(gè)整數(shù)表示答案。

樣例一

input

6 7 1 5 1 2 2 2 3 4 3 4 3 4 5 5 3 5 9 1 6 10 6 5 13 4 3 4 2 6

output

23 15 23 14

限制與約定

對于 100%?的數(shù)據(jù)，1≤S,T,x,y,k≤n≤10^5?;1≤Q≤10^5?;1≤m≤2×10^5?;0≤z≤10^9

?

?

Solution

題意為：給定一個(gè)，多次詢問任意刪掉一個(gè)點(diǎn)之后，S到T的最短路。

首先，這是一個(gè)，因此S到T的最短路是可以沿拓?fù)湫駾P直接求出的，因此我們不花半點(diǎn)力氣，就得到了一個(gè)的算法。

?

現(xiàn)在我們考慮刪點(diǎn)對于一個(gè)的影響，即之前通過拓?fù)湫蚯蟪龅耐負(fù)鋱D其中一個(gè)點(diǎn)不能通過。

先特判S到T不連通的情況，直接輸出-1即可。

現(xiàn)在我們保證了S到T有一條可行路徑?？紤]拓?fù)鋱D之外的邊對其影響，它們會(huì)提供一種可行的方式跨過被刪點(diǎn)連向之后的節(jié)點(diǎn)，形成最短路的總代價(jià)為??? ?，而這一條路會(huì)對在拓?fù)鋱D中u,v兩點(diǎn)之間所有點(diǎn)產(chǎn)生相同的影響。即u,v之間所有點(diǎn)形成的最短路，都能用這一條邊形成的路徑代替（不保證最短，只保證可行）。

于是問題變成了：一堆邊會(huì)改變拓?fù)湫蛑羞B續(xù)的一段區(qū)間[l,r]的點(diǎn)的代價(jià)，求任意某點(diǎn)的最優(yōu)代價(jià)。區(qū)間修改+單點(diǎn)查詢，線段樹維護(hù)最小值即可。

時(shí)間復(fù)雜度為????。

?

#include <vector> #include <list> #include <map> #include <set> #include <deque> #include <queue> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <cctype> #include <string> #include <cstring> #include <ctime> #include <cassert> #include <string.h>#define MP(A,B) make_pair(A,B) #define PB(A) push_back(A) #define SIZE(A) ((int)A.size()) #define LEN(A) ((int)A.length()) #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define fi first #define se secondusing namespace std;template<typename T>inline bool upmin(T &x,T y) { return y<x?x=y,1:0; } template<typename T>inline bool upmax(T &x,T y) { return x<y?x=y,1:0; }typedef long long ll; typedef unsigned long long ull; typedef long double lod; typedef pair<int,int> PR; typedef vector<int> VI;const lod eps=1e-11; const lod pi=acos(-1); const int oo=1<<30; const ll loo=1ll<<62; const int mods=1e9+7; const ll INF=1ll<<60; const int MAXN=1e5+500; /*--------------------------------------------------------------------*/ struct enode{int v; ll c; }; vector<enode> e1[MAXN],e2[MAXN]; int d1[MAXN],d2[MAXN],dfn[MAXN]; ll f1[MAXN],f2[MAXN]; queue<int> que; inline int read() {int f=1,x=0; char c=getchar();while (c<'0'||c>'9') { if (c=='-') f=-1; c=getchar(); }while (c>='0'&&c<='9') { x=(x<<3)+(x<<1)+c-'0'; c=getchar(); }return x*f; } inline char readc() {char c=getchar();while (!isalnum(c)) c=getchar();return c; } struct Segment_Tree {struct treenode{int l,r; ll s; } tree[MAXN<<2];void build(int x,int l, int r){tree[x].s=INF;if ((tree[x].l=l)==(tree[x].r=r)) return;int mid=(tree[x].l+tree[x].r)>>1;build(x<<1,l,mid);build(x<<1|1,mid+1,r);}void change(int x,int L,int R,ll val){if (L<=tree[x].l&&tree[x].r<=R) { tree[x].s=min(tree[x].s,val); return; }int mid=(tree[x].l+tree[x].r)>>1;if (L<=mid) change(x<<1,L,R,val);if (mid<R) change(x<<1|1,L,R,val);}ll query(int x,int y){if (tree[x].l==tree[x].r) return tree[x].s;int mid=(tree[x].l+tree[x].r)>>1;if (y<=mid) return min(tree[x].s,query(x<<1,y));else return min(tree[x].s,query(x<<1|1,y));} } segment; int main() {//freopen("shortest.in","r",stdin);//freopen("shortest.out","w",stdout);int n=read(),m=read(),S=read(),T=read();for (int i=1;i<=m;i++){int u=read(),v=read(),c=read();e1[u].push_back((enode){v,c});e2[v].push_back((enode){u,c});d1[v]++; d2[u]++;}int Dfn=0;for (int i=1;i<=n;i++) f1[i]=INF; f1[S]=0;for (int i=1;i<=n;i++) if (d1[i]==0) que.push(i); while (!que.empty()){int q=que.front();dfn[q]=++Dfn;que.pop();for (int i=0;i<e1[q].size();i++){int to=e1[q][i].v,c=e1[q][i].c;d1[to]--;f1[to]=min(f1[to],f1[q]+c);if (d1[to]==0) que.push(to);}}que.push(T);for (int i=1;i<=n;i++) f2[i]=INF; f2[T]=0;for (int i=1;i<=n;i++) if (d2[i]==0) que.push(i);while (!que.empty()){int q=que.front();que.pop();for (int i=0;i<e2[q].size();i++){int to=e2[q][i].v,c=e2[q][i].c;d2[to]--;f2[to]=min(f2[to],f2[q]+c);if (d2[to]==0) que.push(to);}}segment.build(1,1,n);for (int i=1;i<=n;i++) for (int j=0;j<e1[i].size();j++)if (f1[i]!=INF&&f2[e1[i][j].v]!=INF&&dfn[i]+1<dfn[e1[i][j].v]) segment.change(1,dfn[i]+1,dfn[e1[i][j].v]-1,f1[i]+f2[e1[i][j].v]+e1[i][j].c);int Case=read();while (Case--){int x=read();if (f1[x]==INF||f2[x]==INF) printf("%lld\n",f1[T]);else {ll q=segment.query(1,dfn[x]);printf("%lld\n",q==INF?-1:q);}}return 0; }

?

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的[Wannafly挑战赛2D-Delete]最短路的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。