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); } }