1 条题解

  • 0
    @ 2026-6-17 15:59:04

    // 最短路径树+线段树 Dijkstra 算法 O(MlogN)
    #include<bits/stdc++.h>
    #define int long long
    #define pii pair<int,int>
    using namespace std;
    
    const int N=2e5+5;
    int idx=1,h[N],ne[N<<1],ww[N<<1],to[N<<1];
    void add(int a,int b,int c){
      to[++idx]=b,ww[idx]=c,ne[idx]=h[a],h[a]=idx;
    }
    int n,m,q,u[N],v[N],w[N],L[N],R[N],eid[N];
    int d1[N],dn[N],pre[N];
    bool onpath[N];
    
    void dijkstra(int s,int *d,int *p){
      memset(d,0x3f,sizeof d1); d[s]=0;
      priority_queue<pii,vector<pii>,greater<pii> > q;
      q.emplace(0,s);
      while(!q.empty()){
        auto [dd,u]=q.top(); q.pop();
        if(dd!=d[u]) continue;
        for(int j=h[u]; j; j=ne[j]){
          int v=to[j]; int w=ww[j];
          if(d[v]>d[u]+w){
            d[v]=d[u]+w;
            pre[v]=j/2; //记录v点的前驱边编号
            if(!onpath[v]) p[v]=p[u]; //如果v点不在最短路径E上,v继承u的前缀
            q.emplace(d[v],v);
          }
        }
      }
    }
    
    int cnt;
    struct segtree{ //线段树:区间为最短路径E的cnt条边
      #define lc (u<<1)
      #define rc (u<<1|1)
      #define mid ((l+r)>>1)
      int mi[N<<2]; //节点维护不经过最短路径E的边区间[l,r]的最短路
      
      void build(int u=1,int l=1,int r=cnt){
        mi[u]=1e18;
        if(l==r) return;
        build(lc,l,mid),build(rc,mid+1,r);
      }
      void upd(int x,int y,int d,int u=1,int l=1,int r=cnt){ //区修
        if(x>y) return;
        if(x<=l && r<=y) return mi[u]=min(mi[u],d),void(); //标记永久化
        if(x<=mid) upd(x,y,d,lc,l,mid);
        if(y>mid) upd(x,y,d,rc,mid+1,r);
      }
      int ask(int x,int u=1,int l=1,int r=cnt){ //点查
        if(l==r) return mi[u];
        if(x<=mid) return min(mi[u],ask(x,lc,l,mid));
        else return min(mi[u],ask(x,rc,mid+1,r));
      }
    }T;
    
    signed main(){
      cin>>n>>m>>q;
      for(int i=1; i<=m; i++){
        cin>>u[i]>>v[i]>>w[i];
        add(u[i],v[i],w[i]),add(v[i],u[i],w[i]);
      }
      
      dijkstra(n,dn,R); //预处理以n为根的最短路径树的前驱边pre
      L[1]=R[1]=0,onpath[1]=true;
      for(int p=1; p!=n;){
        int i=pre[p]; //取出p点的前驱边i
        eid[i]=++cnt; //给最短路径E的边i编号
        p=(u[i]==p)?v[i]:u[i]; //取出边i的右端点p
        L[p]=R[p]=cnt;  //记录p点的左侧边的编号
        onpath[p]=true; //记录p点在最短路径E上
      }
      dijkstra(1,d1,L); dijkstra(n,dn,R); //预处理 d1,dn,L,R
      
      T.build();
      for(int i=1; i<=m; i++)if(!eid[i]){ //如果i不是最短路径E的边
        int a=u[i],b=v[i];
        T.upd(L[a]+1,R[b],d1[a]+w[i]+dn[b]); //修改不经过最短路径E的边区间[l,r]的最短路
        T.upd(L[b]+1,R[a],d1[b]+w[i]+dn[a]);
      }
      
      for(int i,x; q--;){ //q次询问
        cin>>i>>x;
        if(eid[i]){ //i是最短路径E的边
          if(x<=w[i]) cout<<d1[n]-w[i]+x;
          else cout<<min(d1[n]-w[i]+x, T.ask(eid[i]));
        } 
        else{
          if(x>=w[i]) cout<<d1[n];
          else cout<<min({d1[n], d1[u[i]]+x+dn[v[i]], d1[v[i]]+x+dn[u[i]]});
        }
        cout<<'\n';
      }
      return 0;
    }
    
    • 1

    D95 最短路径树+线段树 Dijkstra 算法 Indecisive Taxi Fee

    信息

    ID
    12500
    时间
    2000ms
    内存
    512MiB
    难度
    10
    标签
    递交数
    2
    已通过
    1
    上传者