ダイクストラ(ABC070D - Transit Tree Path)

atcoder.jp

オリ合宿のバスの中で。ただのダイクストラ。五分。

#include <stdio.h>
#include <stdlib.h>
#include<math.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
#include<set>
#include<cstring>
 
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1001001001
#define LLINF 1001001001001001001
#define mp make_pair
#define pb push_back
#define LLIandI pair<long long int , int>
#define ll long long
struct dijkstra_normal{
    int V;
    long long int *d; 
    vector<pair<int,int> > *edges;
    priority_queue< pair<long long int,int> , vector< pair<long long int,int> >, greater< pair<long long int,int> > > q;
    dijkstra_normal(int N): V(N){
        d=new long long int[N];
        edges=new vector<pair<int,int> > [N];
        rep(i,N){
            d[i]=LLINF;
        }
    }
    void push(int a,int b, int c){
        edges[a].pb( mp(b,c) );
    }
    long long int *solve(int start){
        q.push(mp(0,start));
        while(!q.empty()){
            pair<long long int,int> p=q.top();q.pop();
            int now=p.second;long long int cost=p.first;
            if(d[now]<=cost)continue;
            d[now]=cost;
            rep(e,edges[now].size()){
                int to=edges[now][e].first;int cst=edges[now][e].second;
                if(d[to]>cost+cst){
                    d[to]>cost+cst;
                    q.push(mp(cost+cst,to));
                }
            }
        }
        return d;
    }
    vector<int> return_not_use(){
        delete[] edges;
        delete[] d;
    }
};

int main(void){
    int N,Q,K;
    scanf("%d",&N);
    dijkstra_normal dijk(N);
    rep(i,N-1){
        int a,b,c;
        scanf("%d %d %d",&a,&b,&c);
        a--;b--;
        dijk.push(a,b,c);dijk.push(b,a,c);
    }
    scanf("%d %d",&Q,&K);
    long long int *ans=dijk.solve(K-1);
    rep(i,Q){
        int x,y;
        scanf("%d %d",&x,&y);x--;y--;
        printf("%lld\n",ans[x]+ans[y]);
    }
}