hdu 6393 Traffic Network in Numazu

63 阅读 0 评论 42 点赞

我是靠谱客的博主想人陪小兔子，最近开发中收集的这篇文章主要介绍hdu 6393 Traffic Network in Numazu，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Problem Description

Chika is elected mayor of Numazu. She needs to manage the traffic in this city. To manage the traffic is too hard for her. So she needs your help.
You are given the map of the city —— an undirected connected weighted graph with N nodes and N edges, and you have to finish Q missions. Each mission consists of 3 integers OP, X and Y.
When OP=0, you need to modify the weight of the Xth edge to Y.
When OP=1, you need to calculate the length of the shortest path from node X to node Y.

Input

The first line contains a single integer T, the number of test cases.
Each test case starts with a line containing two integers N and Q, the number of nodes (and edges) and the number of queries. (3≤N≤105)(1≤Q≤105)
Each of the following N lines contain the description of the edges. The ith line represents the ith edge, which contains 3 space-separated integers ui, vi, and wi. This means that there is an undirected edge between nodes ui and vi, with a weight of wi. (1≤ui,vi≤N)(1≤wi≤105)
Then Q lines follow, the ith line contains 3 integers OP, X and Y. The meaning has been described above.(0≤OP≤1)(1≤X≤105)(1≤Y≤105)
It is guaranteed that the graph contains no self loops or multiple edges.

Output

For each test case, and for each mission whose OP=1, print one line containing one integer, the length of the shortest path between X and Y.

Sample Input

2 5 5 1 2 3 2 3 5 2 4 5 2 5 1 4 3 3 0 1 5 1 3 2 1 5 4 0 5 4 1 5 1 5 3 1 2 3 1 3 2 3 4 4 4 5 5 2 5 5 0 1 3 0 4 1 1 1 4

Sample Output

5 6 6 6

思路：提取出一条边，将其变为树，求树上的最短路，直接lca就行，还需要讨论最短路是否经过我们提取的这条边。

提取的边应该是成环的一条，但是直接取最后一条边也过了，很奇怪。

对于修改，直接套上树状数组就行（动态lca是一个模板）

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
#define maxn 100005
typedef long long LL;
struct Edge{
    int to,next,id;
}edge[maxn<<1];
 
int n,a[maxn],head[maxn],dep[maxn<<1],cnt,pos[maxn],dfs_seq[maxn<<1],dfn,f[maxn<<1][20];
int L[maxn],R[maxn],dfs_clock,G[maxn];
LL W[maxn],C[maxn];

inline void add(int u,int v,int id){
    edge[cnt].to=v;
    edge[cnt].next=head[u];
    edge[cnt].id=id;
    head[u]=cnt++;
}
 
inline int lowbit(int x){return (x)&(-x);}
 
void init(){
    memset(head,-1,sizeof(head));
    memset(pos,-1,sizeof(pos));
    memset(C,0,sizeof(C));
    cnt=dfn=0;
    dfs_clock=0;
}
 
void dfs(int u,int deep)
{
    dfs_seq[dfn]=u,dep[dfn]=deep,pos[u]=dfn++;
    L[u]=++dfs_clock;
    for(int i=head[u];~i;i=edge[i].next){
        int v=edge[i].to;
        if(pos[v]==-1){
            G[edge[i].id]=v;                //important
            dfs(v,deep+1);
            dfs_seq[dfn]=u,dep[dfn++]=deep;
        }
    }
    R[u]=dfs_clock;
}
 
void init_RMQ(int n)
{
    for(int i=1;i<=n;++i) f[i][0]=i;
    for(int j=1;(1<<j)<=n;++j)
        for(int i=1;i+(1<<j)-1<=n;++i){
            if(dep[f[i][j-1]]<dep[f[i+(1<<(j-1))][j-1]]) f[i][j]=f[i][j-1];
            else f[i][j]=f[i+(1<<(j-1))][j-1];
        }
}
 
inline int RMQ(int L,int R)
{
    int k=0;
    while(1<<(k+1)<=R-L+1) ++k;
    if(dep[f[L][k]]<dep[f[R-(1<<k)+1][k]]) return f[L][k];
    return f[R-(1<<k)+1][k];
}
 
inline int lca(int u,int v)
{
    if(pos[u]>pos[v]) return dfs_seq[RMQ(pos[v],pos[u])];
    return dfs_seq[RMQ(pos[u],pos[v])];
}
 
inline void update(int i,LL x)
{
    for(;i<=n;i+=lowbit(i)) C[i]+=x;
}
 
inline LL sum(int i)
{
    LL s=0;
    for(;i>0;i-=lowbit(i)) s+=C[i];
    return s;
}

inline LL dist(int u,int v)
{
    return sum(L[u])+sum(L[v])-2*sum(L[lca(u,v)]);
}
 
int main()
{
    #ifndef ONLINE_JUDGE
            freopen("in.txt","r",stdin);
            freopen("out.txt","w",stdout);
    #endif
    int i,u,v,k,q,s,T;
    LL w;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&q);
        init();
        for(i=1;i<=n-1;++i){
            scanf("%d%d%lld",&u,&v,&w);
            add(u,v,i);
            add(v,u,i);
            W[i]=w;
        }
        dfs(1,0);
        init_RMQ(dfn-1);
        int X,Y; LL Z;
        scanf("%d%d%lld",&X,&Y,&Z);               //第n条边
        W[n] = Z;
        for(i=1;i<n;++i){
            update(L[G[i]],W[i]);
            update(R[G[i]]+1,-W[i]);
        }
        
        while(q--){
            scanf("%d",&k);
            if(k==0){
                scanf("%d%lld",&u,&w);
                if(u==n){
                    W[n] = w;   
                }
                else{
                    update(L[G[u]],w-W[u]);
                    update(R[G[u]]+1,-w+W[u]);
                    W[u]=w;
                }
            }
            else{
                scanf("%d%d",&u,&v);
                LL ans=dist(u,v);
                ans=min(ans,dist(u,X)+dist(v,X));
                ans=min(ans,dist(u,Y)+dist(v,Y));
                ans=min(ans,dist(u,X)+dist(v,Y)+Z);
                ans=min(ans,dist(u,Y)+dist(v,X)+Z);
                printf("%lldn",ans);
            }
        }
    }
    return 0;
}