CF843D-DYNAMIC-ShortestPath (Dynamic Short Off)

Dynamic Shortest Path: CF843D Dynamic Shortest Path

Question:
There is a \(n\) a point \(m\) edge directed weighted graph, \ (q\) Inquiries:

1 \(1 v\) Inquiries from \(1\) to the shortest path from \(v\), no solution input-\(1\)

2 \(c\ l_1\ l_2\ …\ l_c\ l_i\ )‘s border rights increase\(1\)

\(q \leqslant 2000 n ,m \leqslant 10^5\)

Problem solution:

Violence \(dij\) is obviously over No, it needs optimization

First of all, we know an optimization method of \(dij\):
Ensure that the edge weights are all positive, and the edge The sum of rights does not exceed \(W\) when

Nature: If you use \(??\) Update the shortest path of the surrounding points \(??\), then
source to \(t\ ) The shortest path length must be greater than to \(??\) The shortest path length.

Use the (bucket) queue of \(0\)~\(W\) Instead of heap

enumerate values ​​from small to large to get the current minimum value. According to the nature, the added element of
must only be added to the back of the value of the current enumeration.

Complexity\(O(m+W)\), now we have to minimize the value range to optimize it

First do the normal \(dij\), and then consider the influence caused by several sides of the side

Let each side\((x,y)\)’s edge weight is \(dis[x]+edge[i]-dis[y]\) span>,

Assuming that the shortest path obtained in this way is \(f[x]\), then \(f[x]\) means the distance between this point in the new image and the increase in the original image

Analysis of \(f[x]\ ) Value range: Update the \(c\) edges once, and the shortest path will increase at most \(c\ ), the shortest path of \(n\) points through \(n-1\) The edge,
the shortest path increase does not exceed \(n-1\), and \(n\)< The range of /span> is \(10^5\), it is acceptable, and the total complexity is \(O(q( m+W))\)

//CF843D-Dynamic-ShortestPath#include #include #include #include  #include #include using namespace std;typedef lon g long LL;#define cls(x) memset(x,0,sizeof(x))#define For(i,j,k) for(register int i=(j);i<=(k);++ i)#define Rep(i,j,k) for(register int i=(j);i>=(k);--i)#define rint register int#define il inlineil int read(int x=0, int f=1,char ch='0'){ while(!isdigit(ch=getchar())) if(ch=='-') f=-1; while(isdigit(ch)) x=x* 10+ch-'0',ch=getchar(); return f*x;}const int N=1e5+5;int head[N],ver[N],nxt[N],edge[N];int n,m,Q,tot;LL d[N],f[N],t; bool v[N];il void add(int x,int y,int z){ ver[++tot]=y; nxt[tot]=head[x]; head[x]=tot; edge[tot]=z; }il void dij(){ priority_queue> q; memset(d,0x3f,sizeof( d)); d[1]=0; q.push(make_pair(0,1)); while(q.size()) {int x=q.top().second; q.pop(); if (v[x]) continue; v[x]=1; for(rint i=head[x];i;i=nxt[i]) {int y=ver[i]; if(d[y]< =d[x]+edge[i]) continue; d[y]=d[x]+edge[i]; q.push(make_pair(-d[y],y));} }}queue q[N];il void work(int maxn){ memset(f,0x3f,sizeof(f)); f[1 ]=0; q[0].push(1); for(rint now=0;now<=t;++now) while(q[now].size()) {int x=q[now]. front(); q[now].pop(); if(f[x]maxn) continue; q[f[y]].push(y); t=max(t,f[y]);}} For(i ,1,n) d[i]=min(d[0],d[i]+f[i]);}int main(){ n=read(); m=read(); Q=read( ); For(i,1,m) {int x=read(),y=read(),z=read(); add(x,y,z);} dij(); while(Q--) {int op=read(); if(op==1) {int x=read(); printf("%lld\n",d[x]>=d[0]?-1:d[x] );} else {int c=read(),k; For(i,1,c) k=read(),++edge[k]; work(min(c,n-1));}} return 0;}