Submission #2544647

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

/**
ワーシャルフロイド
計算量O(n^3)
全体全の最短距離を求める
**/
#define NODE 301
long long dist[NODE][NODE];
void WF(int num)
{
	for(int k = 0; k < num; k++)
	{
		for(int i = 0; i < num; i++)
		{
			for(int j = 0; j < num; j++)
			{
				dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
			}
		}
	}
}

int main()
{
	int H, W;
	cin >> H >> W;
	for(int i = 0; i < 10; i++)
	{
		for(int j = 0; j < 10; j++)
		{
			long long foo;
			cin >> foo;
			dist[i][j] = foo;
		}
	}
	WF(10);
	int sum = 0;
	for(int i = 0; i < H; i++)
	{
		for(int j = 0; j < W; j++)
		{
			int foo;
			cin >> foo;
			if(foo == 1 || foo == -1)
			{
				continue;
			}
			sum += dist[foo][1];
		}
	}
	cout << sum << endl;
	return 0;
}

Submission Info

Judge Result