Traffic Network in Numazu hdu6393

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

不错的题目，比较锻炼代码能力

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>
#include <set>
#include <vector>
using namespace std;
const int maxn = 100000 + 10;
typedef long long ll;
int n,m,dfs_clock,cnt;
int dep[maxn];
int pa[maxn][25],pre[maxn];
int head[maxn];
ll w[maxn];
int far[maxn];
int L[maxn],R[maxn];
ll C[maxn];
int pos[maxn];
struct edge
{
    int to,next,id;
}e[maxn];
void init()
{
    cnt=0;   dfs_clock=0;
    memset(head,-1,sizeof(head));
    memset(pre,0,sizeof(pre));
    memset(dep,0,sizeof(dep));
    for(int i=0;i<=n;i++)
    {
        far[i]=i;
    }
    memset(C,0,sizeof(C));
    memset(pos,0,sizeof(pos));
}
int lowbit(int x)
{
    return x&-x;
}
ll sum(int x)
{
    ll ret=0;
    while(x>0)
    {
        ret+=C[x];
        x-=lowbit(x);
    }
    return ret;
}
void addL(int x,ll d)
{
    while(x<=n)
    {
        C[x]+=d;
        x+=lowbit(x);
    }
}
void add(int u,int v,int id)
{
    e[cnt].to=v;
    e[cnt].next=head[u];
    e[cnt].id=id;
    head[u]=cnt++;
}
void dfs(int u,int f,int deep)
{
    dep[u]=deep; pre[u]=f;
    L[u]=++dfs_clock;
    for(int i=head[u];i!=-1;i=e[i].next)
    {
        int v=e[i].to;
        if(v==f)continue;
        pos[e[i].id]=v;
        dfs(v,u,deep+1);
    }
    R[u]=dfs_clock;
}
void make_pa()
{
    memset(pa,-1,sizeof(pa));
    for(int i=1;i<=n;i++) pa[i][0]=pre[i];
    for(int j=1;(1<<j)<n;j++)
        for(int i=1;i<=n;i++)
         if(pa[i][j-1]!=-1)
         pa[i][j]=pa[pa[i][j-1]][j-1];
}
int lca(int x,int y)
{
    int i;
    if(dep[x]<dep[y]) swap(x,y);
    for(i=20;i>=0;i--)
    {
        if(dep[x]-(1<<i)>=dep[y]) x=pa[x][i];
    }
    if(x==y) return x;
    for(i=20;i>=0;i--)
    {
        if(pa[x][i]!=-1&&pa[x][i]!=pa[y][i])
        {
            x=pa[x][i],y=pa[y][i];
        }
    }
    return pre[x];
}
int find_(int x)
{
    if(x==far[x]) return far[x];
    return far[x]=find_(far[x]);
}
ll dist(int u,int v)
{
    return sum(L[u])+sum(L[v])-2*sum(L[lca(u,v)]);
}
int main()
{
   // freopen("in.txt","r",stdin);
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        init();
        int x,y,id;
        for(int i=1;i<=n;i++)
        {
            int x1,y1;
            scanf("%d%d%lld",&x1,&y1,&w[i]);
            int x2=find_(x1);
            int y2=find_(y1);
            if(x2==y2)
            {
                x=x1,y=y1,id=i;
            }
            else
            {
                far[y1]=x1;
                add(x1,y1,i);
            }
        }
        dfs(1,1,0);
        make_pa();
        for(int i=1;i<=n;i++)
        {
            if(i!=id)
            {
                addL(L[pos[i]],w[i]);
                addL(R[pos[i]]+1,-w[i]);
            }
        }
        for(int i=1;i<=m;i++)
        {
            int u,op;
            ll v;
            scanf("%d%d%lld",&op,&u,&v);
            if(op==0)
            {
                if(u==id) w[id]=v;
                else
                {
                    addL(L[pos[u]],v-w[u]);
                    addL(R[pos[u]]+1,w[u]-v);
                    w[u]=v;
                }
            }
            else
            {
                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)+w[id]);
                ans=min(ans,dist(u,y)+dist(v,x)+w[id]);
                printf("%lldn",ans);
            }
        }
    }
    return 0;
}

最后

以上就是冷静冬天为你收集整理的Traffic Network in Numazu hdu6393的全部内容，希望文章能够帮你解决Traffic Network in Numazu hdu6393所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。