tozangezan's diary

勝手にソースコードをコピペして利用しないでください。

PKU1986 Distance Queries

やるだけだけど、グラフの実装をしたということで。過去にひどいソースを書いていた頃由は綺麗なソースになりました。

#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
int segtree[262144];
vector<pair<int,int> > g[40000];
int num[131072];
int cost[40000];
int use[40000];
char str[2];
int now;
int p;
int ptoc[40000];
void dfs(int a,int b,int c){
        use[a]=now;
        int u=p;
        num[now++]=p++;
        ptoc[p-1]=a;
        cost[a]=c;
        for(int i=0;i<g[a].size();i++){
                if(g[a][i].first!=b){
                        dfs(g[a][i].first,a,c+g[a][i].second);
                        num[now++]=u;
                }
        }
}
int query(int a,int b,int c,int d,int e){
        if(a>d||b<c)return 999999999;
        if(c<=a&&b<=d)return segtree[e];
        return min(query(a,(a+b)/2,c,d,e*2),query((a+b)/2+1,b,c,d,e*2+1));
}
void set(int a,int b){
        a+=131072;
        while(a){
                segtree[a]=min(segtree[a],b);
                a/=2;
        }
}
int main(){
        int a,b;
        for(int i=0;i<262144;i++)segtree[i]=999999999;
        scanf("%d%d",&a,&b);
        for(int i=0;i<b;i++){
                int c,d,e;
                scanf("%d%d%d%s",&c,&d,&e,str);
                g[c-1].push_back(make_pair(d-1,e));
                g[d-1].push_back(make_pair(c-1,e));
        }
        dfs(0,-1,0);
        for(int i=0;i<now;i++)set(i,num[i]);
        int c;
        scanf("%d",&c);
        for(int i=0;i<c;i++){
                int d,e;
                scanf("%d%d",&d,&e);
                d--;
                e--;
        //      printf("%d ",query(0,131071,min(use[d],use[e]),max(use[d],use[e]),1));
                printf("%d\n",cost[d]+cost[e]-cost[ptoc[query(0,131071,min(use[d],use[e]),max(use[d],use[e]),1)]]*2);
        }
}