Submission #2209962

---

Source Code Expand

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

struct Node
{
	int idx;
	int cost;
	bool operator < (const  Node& n) const {
		return cost < n.cost;
	}
	bool operator > (const  Node& n) const {
		return cost > n.cost;
	}
};

class Solver
{
private:
	int h;
	int w;
	vector<vector<int> > edge;
	vector<int> nums_map;
public:
	Solver() {
		cin >> h >> w;
		for (int i = 0; i < 10; ++i)
		{
			vector<int> v_tmp;
			for (int j = 0; j < 10; ++j)
			{
				int tmp;
				cin >> tmp;
				v_tmp.push_back(tmp);
			}
			edge.push_back(v_tmp);
		}
		nums_map = vector<int>(10, 0);
		for (int i = 0; i < h; ++i)
		{
			for (int j = 0; j < w; ++j)
			{
				int tmp;
				cin >> tmp;
				if(tmp == -1) continue;
				nums_map[tmp]++;
			}
		}
	}
	int dijkstra(int from) {
		Node s_node = {from, 0};
		vector<int> min_cost;
		min_cost = vector<int>(10, -1);
		priority_queue<Node, vector<Node>, greater<Node> > pq;
		pq.push(s_node);
		while(!pq.empty()) {
			Node cur_node = pq.top();
			pq.pop();
			// cout << cur_node.idx << " " << cur_node.cost << endl;
			if(min_cost[cur_node.idx] == -1) {
				min_cost[cur_node.idx] = cur_node.cost;
			} else {
				continue;
			}
			for (int i = 0; i < 10; ++i)
			{
				Node next_node = {i, cur_node.cost + edge[cur_node.idx][i]};
				// cout << next_node.idx << " " << next_node.cost << endl;
				if(min_cost[i] != -1) {
					continue;
				}
				pq.push(next_node);
			}
		}
		return min_cost[1];
	}
	void exec() {
		int min_cost[10];
		for (int i = 0; i < 10; ++i)
		{
			min_cost[i] = dijkstra(i);
		}
		long ans = 0;
		for (int i = 0; i < 10; ++i)
		{
			ans += min_cost[i] * nums_map[i];
		}
		cout << ans << endl;
	}
};


int main() {
	Solver s = Solver();
	s.exec();
}

Submission Info

Judge Result