AtCoder が提供しているABC(AtCoder Beginner Contest)079 D問題をC++で解いてみました。ABC079は、2017年11月18日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 Wall(Difficulty : 949)
問題の詳細は、リンク先をご覧ください。
すべての数を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 の問題を紹介していきます。