FIRETRUCKS(소방차)

(출처) https://algospot.com/judge/problem/read/FIRETRUCKS

코드

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

using namespace std;
vector<vector<pair<int, int>>> seoul;
const int INF = numeric_limits<int>::max();

vector<int> firetrucks(int v) {
	vector<int> dist(v + 1, INF);
	priority_queue<pair<int, int>> p_q;
	p_q.push(pair<int, int>(0, 0));
	dist[0] = 0;
	while (!p_q.empty()) {
		int here = p_q.top().second;
		int cost = -p_q.top().first;
		p_q.pop();
		if (dist[here] < cost) continue;
		
		for (int i = 0; i < seoul[here].size(); i++) {
			int there = seoul[here][i].first;
			int next_cost = cost + seoul[here][i].second;
			if (dist[there] > next_cost) {
				dist[there] = next_cost;
				p_q.push(pair<int, int>(-next_cost, there));
			}
		}
	}
	return dist;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int tc;
	cin >> tc;

	while (tc--) {
		int v, e, n, m;
		cin >> v >> e >> n >> m;
		seoul = vector<vector<pair<int, int>>> (v + 1);
		for (int i = 0; i < e; i++) {
			int a, b, dist;
			cin >> a >> b >> dist;
			seoul[a].push_back(pair<int, int>(b, dist));
			seoul[b].push_back(pair<int, int>(a, dist));
		}
		vector<int> target;
		for (int i = 0; i < n; i++) {
			int temp_target;
			cin >> temp_target;
			target.push_back(temp_target);
		}

		for (int i = 0; i < m; i++) {
			int fire_station;
			cin >> fire_station;
			seoul[0].push_back(pair<int, int>(fire_station, 0));
		}

		int ret = 0;
		vector<int> dist = firetrucks(v);
		for (int i = 0; i < target.size(); i++) {
			ret += dist[target[i]];
		}

		cout << ret << "\n";
	}

	return 0;
}