# CF843D-Dynamic-ShortestPath(动态最短路)

#### 动态最短路：CF843D Dynamic Shortest Path

`1` \(1 v\) 询问从\(1\)\(v\)的最短路，无解输-\(1\)

`2` \(c\ l_1\ l_2\ ...\ l_c\ l_i\)的边权增加\(1\)

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

\(0\)~\(W\) 的(桶)队列代替堆

```//CF843D-Dynamic-ShortestPath
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <queue>
using namespace std;

typedef long 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 inline

il 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 n,m,Q,tot;
LL d[N],f[N],t; bool v[N];
il void add(int x,int y,int z)

il void dij()
{
priority_queue<pair<LL,int> > 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;
{
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<int> 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]<now) continue;
//一个点可能被插入多个队列中
{
int y=ver[i],z=d[x]+edge[i]-d[y];
if(f[y]<=f[x]+z) continue;
f[y]=f[x]+z; if(f[y]>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()
{
dij();
while(Q--)
{
if(op==1)
{