生物制药公司网站模板,设计logo网站免费南蒲四特,网站建设行业 知乎,电子商务公司是做什么的[Wannafly挑战赛2D-Delete]最短路
题目描述
给定一张 n 个点#xff0c;m 条边的带权有向无环图#xff0c;同时给定起点 S 和终点 T #xff0c;一共有 q 个询问#xff0c;每次询问删掉某个点和所有与它相连的边之后 S 到 T 的最短路#xff0c;询问之间互相独立(即删…[Wannafly挑战赛2D-Delete]最短路
题目描述
给定一张 n 个点m 条边的带权有向无环图同时给定起点 S 和终点 T 一共有 q 个询问每次询问删掉某个点和所有与它相连的边之后 S 到 T 的最短路询问之间互相独立(即删除操作在询问结束之后会立即撤销)如果删了那个点后不存在 S 到 T 的最短路则输出 −1 。点的编号为 1 到 n 。
输入格式
第一行四个正整数表示 n,m,S,T 意义如题所述。
接下来 m 行每行三个正整数 x,y,z 表示有一条 x 到 y 的有向边权值为 z 。
接下来一行一个正整数 Q 表示询问次数。
最后 Q 行每行一个正整数 k 表示这次询问要删除点 k 。
输出格式
输出 Q 行每行一个整数表示答案。
样例一
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% 的数据1≤S,T,x,y,k≤n≤10^5 ;1≤Q≤10^5 ;1≤m≤2×10^5 ;0≤z≤10^9 Solution
题意为给定一个多次询问任意删掉一个点之后S到T的最短路。
首先这是一个因此S到T的最短路是可以沿拓扑序DP直接求出的因此我们不花半点力气就得到了一个的算法。 现在我们考虑删点对于一个的影响即之前通过拓扑序求出的拓扑图其中一个点不能通过。
先特判S到T不连通的情况直接输出-1即可。
现在我们保证了S到T有一条可行路径。考虑拓扑图之外的边对其影响它们会提供一种可行的方式跨过被删点连向之后的节点形成最短路的总代价为 而这一条路会对在拓扑图中u,v两点之间所有点产生相同的影响。即u,v之间所有点形成的最短路都能用这一条边形成的路径代替不保证最短只保证可行。
于是问题变成了一堆边会改变拓扑序中连续的一段区间[l,r]的点的代价求任意某点的最优代价。区间修改单点查询线段树维护最小值即可。
时间复杂度为 。 #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;templatetypename Tinline bool upmin(T x,T y) { return yx?xy,1:0; }
templatetypename Tinline bool upmax(T x,T y) { return xy?xy,1:0; }typedef long long ll;
typedef unsigned long long ull;
typedef long double lod;
typedef pairint,int PR;
typedef vectorint VI;const lod eps1e-11;
const lod piacos(-1);
const int oo130;
const ll loo1ll62;
const int mods1e97;
const ll INF1ll60;
const int MAXN1e5500;
/*--------------------------------------------------------------------*/
struct enode{int v; ll c; };
vectorenode e1[MAXN],e2[MAXN];
int d1[MAXN],d2[MAXN],dfn[MAXN];
ll f1[MAXN],f2[MAXN];
queueint que;
inline int read()
{int f1,x0; char cgetchar();while (c0||c9) { if (c-) f-1; cgetchar(); }while (c0c9) { x(x3)(x1)c-0; cgetchar(); }return x*f;
}
inline char readc()
{char cgetchar();while (!isalnum(c)) cgetchar();return c;
}
struct Segment_Tree
{struct treenode{int l,r; ll s; } tree[MAXN2];void build(int x,int l, int r){tree[x].sINF;if ((tree[x].ll)(tree[x].rr)) return;int mid(tree[x].ltree[x].r)1;build(x1,l,mid);build(x1|1,mid1,r);}void change(int x,int L,int R,ll val){if (Ltree[x].ltree[x].rR) { tree[x].smin(tree[x].s,val); return; }int mid(tree[x].ltree[x].r)1;if (Lmid) change(x1,L,R,val);if (midR) change(x1|1,L,R,val);}ll query(int x,int y){if (tree[x].ltree[x].r) return tree[x].s;int mid(tree[x].ltree[x].r)1;if (ymid) return min(tree[x].s,query(x1,y));else return min(tree[x].s,query(x1|1,y));}
} segment;
int main()
{//freopen(shortest.in,r,stdin);//freopen(shortest.out,w,stdout);int nread(),mread(),Sread(),Tread();for (int i1;im;i){int uread(),vread(),cread();e1[u].push_back((enode){v,c});e2[v].push_back((enode){u,c});d1[v]; d2[u];}int Dfn0;for (int i1;in;i) f1[i]INF; f1[S]0;for (int i1;in;i) if (d1[i]0) que.push(i); while (!que.empty()){int qque.front();dfn[q]Dfn;que.pop();for (int i0;ie1[q].size();i){int toe1[q][i].v,ce1[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 i1;in;i) f2[i]INF; f2[T]0;for (int i1;in;i) if (d2[i]0) que.push(i);while (!que.empty()){int qque.front();que.pop();for (int i0;ie2[q].size();i){int toe2[q][i].v,ce2[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 i1;in;i) for (int j0;je1[i].size();j)if (f1[i]!INFf2[e1[i][j].v]!INFdfn[i]1dfn[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 Caseread();while (Case--){int xread();if (f1[x]INF||f2[x]INF) printf(%lld\n,f1[T]);else {ll qsegment.query(1,dfn[x]);printf(%lld\n,qINF?-1:q);}}return 0;
}
