(BOJ) 14618 총깡 총깡

문제: https://www.acmicpc.net/problem/14618

 

문제풀이:

1. 진서집에서 시작해서 다익스트라 돌리기 (양방향)

2. 진서가 가장 빨리 갈 수 있는 집 찾기 

   B집부터 비교해서 갱신해주고

   그 후, A집 비교해줘서 B집이랑 같은 거리이면 A 출력하기

 

소스코드:

#define inf 987654321
using namespace std;

typedef pair<int, int> P;
int n, m, jinsu, k,dist[5001];
bool visit[5001];
vector<int> a, b;
vector<vector<P>> adj;
priority_queue<P, vector<P>, greater<P>> pq;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);

	cin >> n >> m;
	cin >> jinsu >> k;

	for (int i = 0; i < k; i++) {
		int q;
		cin >> q;
		a.push_back(q);
	}
	for (int i = 0; i < k; i++) {
		int q;
		cin >> q;
		b.push_back(q);
	}
	adj.resize(n + 1);
	for (int i = 0; i < m; i++) {
		int q, w, e;
		cin >> q >> w >> e;
		adj[q].push_back({ w,e });
		adj[w].push_back({ q,e });
	}
	fill(dist, dist + n + 1, inf);
	dist[jinsu] = 0;
	pq.push({ 0,jinsu });

	while (!pq.empty()) {
		int cur;
		do {
			cur = pq.top().second;
			pq.pop();
		} while (!pq.empty() && visit[cur]);
		if (visit[cur]) break;
		visit[cur] = true;

		for (int i = 0; i < adj[cur].size(); i++) {
			if (dist[adj[cur][i].first] > dist[cur] + adj[cur][i].second) {
				dist[adj[cur][i].first] = dist[cur] + adj[cur][i].second;
				pq.push({ dist[adj[cur][i].first],adj[cur][i].first });
			}
		}
	}
	int res = inf;
	char res2;
	for (int i = 0; i < b.size(); i++) {
		if (dist[b[i]] < res) {
			res = dist[b[i]];
			res2 = 'B';
		}
	}
	for (int i = 0; i < a.size(); i++) {
		if (dist[a[i]] <= res) {
			res = dist[a[i]];
			res2 = 'A';
		}
	}
	if (res == inf) {
		cout << "-1\n";
	}
	else {
		cout << res2 << '\n' << res << '\n';
	}

	return 0;
}