취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 6248번 문제인 Bronze Cow Party이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/6248

$X$에서 어떤 지점까지 이동하는 데에 드는 최소 시간을 구할 수 있다면 그 지점까지 갔다가 돌아오는 데에 드는 최소시간은 그 두 배임을 알 수 있다.

따라서 각 지점까지 이동하는 데에 드는 최소 시간을 각각 구하고, 그 중 가장 큰 값을 찾아 문제의 답을 계산할 수 있다.

음이 아닌 가중치를 갖는 그래프에서의 한 꼭짓점에서 다른 모든 꼭짓점까지의 최단거리는 다익스트라 알고리즘을 이용해 간단히 구할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

int N, M, S;
vector<pair<int, int>> G[1001];
int dist[1001];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
int mx;

void dijkstra() {
	memset(dist, 0x3f, sizeof(dist));
	dist[S] = 0;
	pq.push(make_pair(0, S));
	while (!pq.empty()) {
		int cur = pq.top().second, d = pq.top().first; pq.pop();
		if (dist[cur] < d) continue;
		mx = dist[cur];
		for (auto &p : G[cur]) {
			int nxt = p.first, dd = p.second + d;
			if (dist[nxt] > dd) dist[nxt] = dd, pq.push(make_pair(dd, nxt));
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> M >> S;
	while (M--) {
		int x, y, w; cin >> x >> y >> w;
		G[x].emplace_back(make_pair(y, w));
		G[y].emplace_back(make_pair(x, w));
	}

	dijkstra();
	cout << mx * 2;
}