백준 1238 c++ - [PlusUltraCode]

 

[필자 사고]

 

문제를 분석해 보면 X라는 지점에 간 거리와
X에서 부터 본래의 자기 집으로 간 거리의 합이 가장 긴 값을 구하는 문제이다.

 

다익스트라 알고리즘을 사용하면 쉽게 풀 수 있는 문제이다.

1. 각 지점에서 다익스트라 알고리즘을 사용하고 X까지의 거리를 임의이 배열에 저장해 놓는다.

2. 다음으로 X에서 다익스트라 알고리즘을 사용하여 임의의 배열에 더하여 저장해 놓는다.

3. 임의이 배열에서 가장 큰 값이 정답이다.

 

[소스 코드]

#include <iostream>
#include <vector>
#include <queue>
#include<climits>
#include <algorithm>
using namespace std;

int N, M, X;

typedef pair<int, int> Node;
vector<vector<Node>> Arr;
vector<bool> visited;
vector<int> pathLoad;
vector<int> pathLoad2;
priority_queue<Node, vector<Node>, greater<Node>> pq;
void Input() {
	cin >> N >> M >> X;
	Arr.resize(N + 1);
	visited.resize(N + 1, false);
	pathLoad2.resize(N + 1, 0);
	pathLoad.resize(N + 1, INT_MAX);
	for (int i = 0; i < M; i++) {
		int start, end, weight;
		cin >> start >> end >> weight;
		Arr[start].push_back({ weight,end });

	}

}

void Init() {
	pathLoad.clear();
	visited.clear();
	pathLoad.resize(N + 1, INT_MAX);
	visited.resize(N + 1, false);

}

void Solve() {

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

		if (i == X)continue;

		pq.push({ 0,i });
		pathLoad[i] = 0;
		while (!pq.empty()) {
			int nowIdx = pq.top().second;
			pq.pop();
			if (visited[nowIdx] == true)continue;
			visited[nowIdx] = true;
			for (Node nextNode : Arr[nowIdx]) {
				int nextIdx = nextNode.second;
				int nextWeight = nextNode.first;
				if (visited[nextIdx] == false &&
					pathLoad[nextIdx] > pathLoad[nowIdx] + nextWeight) {
					pathLoad[nextIdx] = pathLoad[nowIdx] + nextWeight;
					pq.push({ pathLoad[nextIdx],nextIdx });
				}
			}
		}
		pathLoad2[i] = pathLoad[X];

		Init();
	}


	pq.push({ 0,X });
	pathLoad[X] = 0;
	while (!pq.empty()) {
		int nowIdx = pq.top().second;
		pq.pop();
		if (visited[nowIdx] == true)continue;
		visited[nowIdx] = true;
		for (Node nextNode : Arr[nowIdx]) {
			int nextIdx = nextNode.second;
			int nextWeight = nextNode.first;
			if (visited[nextIdx] == false &&
				pathLoad[nextIdx] > pathLoad[nowIdx] + nextWeight) {
				pathLoad[nextIdx] = pathLoad[nowIdx] + nextWeight;
				pq.push({ pathLoad[nextIdx],nextIdx });
			}
		}
	}


	for (int i = 0; i <= N; i++) {
		if (pathLoad[i] == INT_MAX || pathLoad2[i] == INT_MAX) {
			continue;
		}
		pathLoad2[i] += pathLoad[i];

	}
	cout << *max_element(pathLoad2.begin(), pathLoad2.end());


}

int main(void) {
	Input();
	Solve();
}