AtCoder

ABC070 D問題(Transit Tree Path)を解く

AtCoder_ABC070_D

AtCoder が提供しているABC(AtCoder Beginner Contest)070 D問題をC++で解いてみました。ABC070は、2017年8月12日21:00に実施されました。

AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。

D問題 Transit Tree Path(Difficulty : 1182)

問題の詳細は、リンク先をご覧ください。

ABC070 D問題 Transit Tree Path

頂点Kからの他の頂点への距離を求めておきます。AtCoder Problems による Difficulty は 1182 でした。

解答案

C++ プログラム例(ABC070D)

頂点Kから他の頂点への最短距離をBFSで求めておきます。クエリで与えられる頂点Xiから頂点Kまでの最短距離と頂点yiから頂点Kまでの最短距離の和を出力します。

以下が、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 の問題を紹介していきます。

COMMENT

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

CAPTCHA