cf 843 D Dynamic Shortest Path [最短路+bfs]

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题面：

传送门

思路：

真·动态最短路

但是因为每次只加1

所以可以每一次修改操作的时候使用距离分层的bfs，在O(n)的时间内解决修改

这里要用到一个小技巧：

把每条边(u,v)的边权表示为dis[u]+w(u,v)-dis[v]，这样边权实际上变成了“这条边离作为最短路的一份子还差了多少”

然后在用这个边权的新图里面更新1到每个点的最短路，再用原来的dis加上这个值，就是当前的最短路了

实际上是把绝对数值转化为了“离最优解的距离”，以此解题

Code：

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<queue>

 #define ll long long

 #define inf 1e15

 #define mp make_pair

 using namespace std;

 inline int read(){

     int re=,flag=;char ch=getchar();

     while(ch>''||ch<''){

         if(ch=='-') flag=-;

         ch=getchar();

     }

     while(ch>=''&&ch<='') re=(re<<)+(re<<)+ch-'',ch=getchar();

     return re*flag;

 }

 int n,m,cnt,first[];ll dis[];

 struct edge{

     int to,next,w;

 }a[];

 inline void add(int u,int v,int w){

     a[++cnt]=(edge){v,first[u],w};first[u]=cnt;

 }

 struct node{

     int x;node(){x=;}

     node(int xx){x=xx;}

     bool operator <(node r) const {

         return dis[x]>dis[r.x];

     }

 };

 int delta[];

 priority_queue<node>qq;

 void spfa(){

     int i,u,v;

     for(i=;i<=n;i++) dis[i]=inf;

     dis[]=;qq.push(node());

     while(!qq.empty()){

         u=qq.top().x;qq.pop();

         for(i=first[u];~i;i=a[i].next){

             v=a[i].to;

             if(dis[v]>dis[u]+(ll)a[i].w){

                 dis[v]=dis[u]+(ll)a[i].w;

                 qq.push(node(v));

             }

         }

     }

 }

 queue<int>q[];

 void bfs(){

     memset(delta,0x3f,sizeof(delta));

     int i,j,u,v,w,maxn,head=,tail=;

     q[].push();delta[]=maxn=;

     for(i=;i<=maxn;i++){

         while(!q[i].empty()){

             u=q[i].front();q[i].pop();

             if(i>delta[u]) continue;

             for(j=first[u];~j;j=a[j].next){

                 v=a[j].to;w=a[j].w;

                 if(delta[v]>delta[u]+dis[u]+w-dis[v]){

                     delta[v]=delta[u]+dis[u]+w-dis[v];

                     if(delta[v]<=n){

                         q[delta[v]].push(v);maxn=max(maxn,delta[v]);

                     }

                 }

             }

         }

     }

 }

 int main(){

 //    freopen("d.in","r",stdin);

     memset(first,-,sizeof(first));

     int i,j,t1,t2,t3,Q;

     n=read();m=read();Q=read();

     for(i=;i<=m;i++){

         t1=read();t2=read();t3=read();

         add(t1,t2,t3);

     }

     spfa();

     for(i=;i<=Q;i++){

         t1=read();

         if(t1==) t2=read(),printf("%I64d\n",(dis[t2]>=inf)?-:dis[t2]);

         else{

             t2=read();

             memset(delta,,sizeof(delta));

             for(j=;j<=t2;j++) t3=read(),a[t3].w++;

             bfs();

             for(j=;j<=n;j++) dis[j]+=(ll)delta[j];

 //            cout<<endl;

         }

     }

 //    system("pause");

     return ;

 }