백준 1238, 파티

문제

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

풀이

그냥 우선순위큐로 최적화한 다익스트라를 많이 많이 돌리는 문제이다. 이외의 별다른 풀이는 없다. 저번에 최적화 다익스트라를 처음 사용해봐서 익숙해질겸 풀어봤다.

실수

• 구현하는데 거진 30분 이상 걸린 것 같다. 생각과 코드 구현의 괴리가 많았다.(생각은 맞았는데 그걸 그대로 코드로 작성할때 실수가 많이 나옴) 제대로 생각하고 코드를 작성하자 (cost 변경 안해줌)

코드

#define _CRT_SECURE_NO_WARNINGS

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

using namespace std;

vector<vector<pair<int, int>>> graph(1001, vector<pair<int, int>>(0, make_pair(0, 0)));
vector<int> cost(1001, 2e9);
vector<int> visit(1001, 0);

int n, m, x;

int dijkstra(int start, int dest) {

	pair<int, int> temp;

	if (start == dest)
		return 0;

	// 초기화
	for (int i = 1; i <= n; i++) {

		cost[i] = 2e9;
		visit[i] = 0;

	}

	priority_queue<pair<int, int>> pq;

	pq.push(make_pair(0, start));
	cost[start] = 0;

	while (!pq.empty()) {

		while (!pq.empty() && visit[pq.top().second] == 1)
			pq.pop();

		if (pq.empty())
			break;

		temp = pq.top();
		pq.pop();

		visit[temp.second] = 1;

		for (int i = 0; i < graph[temp.second].size(); i++) {

			if (cost[graph[temp.second][i].first] > cost[temp.second] + graph[temp.second][i].second) { // 최소비용 갱신
				
				cost[graph[temp.second][i].first] = cost[temp.second] + graph[temp.second][i].second;
				pq.push(make_pair((cost[temp.second] + graph[temp.second][i].second) * -1, graph[temp.second][i].first));

			}

		}

	}

	return cost[dest];
	

}

int main() {

	int temp1, temp2, temp3;
	int res = 0;

	scanf("%d %d %d", &n, &m, &x);

	for (int i = 0; i < m; i++) {

		scanf("%d %d %d", &temp1, &temp2, &temp3);

		graph[temp1].push_back(make_pair(temp2, temp3));

	}

	for (int i = 1; i <= n; i++) {

		res = max(res, dijkstra(i, x) + dijkstra(x, i));

	}

	printf("%d", res);

	return 0;

}