AtCoder

ABC079 D問題(Wall)を解く

AtCoder_ABC079_D

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

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

D問題 Wall(Difficulty : 949)

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

ABC079 D問題 Wall

すべての数を1に変換する魔力を求めます。AtCoder Problems による Difficulty は 949 でした。

解答案

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

ワーシャル・フロイド法が適用できる典型的な問題です。すべての数から他の数への変換に必要な魔力を事前に求め、その結果を使用します。

以下が、C++プログラムです。

#include <bits/stdc++.h>
using namespace std;

#define INF (1 << 30)

int main()
{
	int h, w;
	cin >> h >> w;
	int n = 10;
	vector<vector<int>> dist(n, vector<int>(n, INF));
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			cin >> dist[i][j];
		}
	}

	for (int k = 0; k < n; ++k) {
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < n; ++j) {
				if ((dist[i][k] < INF) && (dist[k][j] < INF)) {
					dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
				}
			}
		}
	}

	int result = 0;
	for (int i = 0; i < h; ++i) {
		for (int j = 0; j < w; ++j) {
			int a;
			cin >> a;
			if (a == -1) {
				continue;
			}
			result += dist[a][1];
		}
	}

	cout << result << endl;

	return 0;
}

AC(Accepted=正しいプログラム)と判定されました。

最後に

今回は、典型的な問題を紹介しました。

引き続き ABC の問題を紹介していきます。

COMMENT

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

CAPTCHA