AtCoder が提供しているABC（AtCoder Beginner Contest）070 D問題をC++で解いてみました。ABC070は、2017年8月12日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 Transit Tree Path（Difficulty : 1182）
問題の詳細は、リンク先をご覧ください。
頂点Kからの他の頂点への距離を求めておきます。AtCoder Problems による Difficulty は 1182 でした。
解答案
C++ プログラム例（ABC070D）
頂点
以下が、C++プログラムです。
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define INF (1LL << 60)
struct Edge {
int to;
ll weight;
Edge() {}
Edge(int t, ll w) : to(t), weight(w) {}
};
int main()
{
int n;
cin >> n;
vector<vector<Edge>> G(n);
for (int i = 0; i < n - 1; ++i) {
int a, b;
ll c;
cin >> a >> b >> c;
--a;
--b;
G[a].push_back(Edge(b, c));
G[b].push_back(Edge(a, c));
}
int q, k;
cin >> q >> k;
--k;
vector<ll> dist(n, INF);
queue<int> que;
dist[k] = 0;
que.push(k);
while (!que.empty()) {
int now = que.front();
que.pop();
for (auto next_v : G[now]) {
if (dist[next_v.to] == INF) {
dist[next_v.to] = dist[now] + next_v.weight;
que.push(next_v.to);
}
}
}
for (int i = 0; i < q; ++i) {
int x, y;
cin >> x >> y;
--x;
--y;
cout << dist[x] + dist[y] << endl;
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
最後に
最短経路を求める問題に帰着させました。
引き続き ABC の問題を紹介していきます。
