백준 1504 c++ - [PlusUltraCode]

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

 

 

[필자 사고]

 

그래프 최단거리를 물어보는 문제이다.

 

특이한 점은 특정 A ,B를 반드시 경유해야 된다는 점이다

 

다익스트라의 활용도를 극한으로 올려줄 수 있는 문제라고 생각한다.

 

 

start -> A-> B -> N 인 경우와

start -> B -> A -> N 인 경우가 있다.

 

다익스트라를 하나 하나 사용하여 각 start->A  와 A->B 와 B->N인 각각의 최단 경로를 합한다.

그 다음 저 두 경로중 작은 값을 출력하면 된다.

 

[소스 코드]

 

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

typedef pair<int, int> Node;

vector<vector<Node>> Arr;
vector<bool> visited;
vector<int> pathLoad;
bool check = true;
int N, M, A, B;

void Dijkstra(int start) {
	priority_queue<Node, vector<Node>, greater<Node>> pq;
	pq.push({ 0,start });
	pathLoad[start] = 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 nextCost = nextNode.first;

			if (visited[nextIdx] == false &&
				pathLoad[nextIdx] > pathLoad[nowIdx] + nextCost) {
				pathLoad[nextIdx] = pathLoad[nowIdx] + nextCost;
				pq.push({ pathLoad[nextIdx],nextIdx });
			}
		}
	}


}

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

}

void Input() {
	cin >> N >> M;
	Arr.resize(N + 1);
	Init();
	for (int i = 0; i < M; i++) {
		int s, e, w;
		cin >> s >> e >> w;
		Arr[s].push_back({ w,e });
		Arr[e].push_back({ w,s });

	}
	cin >> A >> B;
}

void checkLoad(int end) {
	if (pathLoad[end] == INT_MAX) {
		check = false;
		return;
	}
}

int main(void) {
	Input();
	Dijkstra(1);
	checkLoad(A);
	checkLoad(B);
	checkLoad(N);
	int SA, AB, BN;
	int SB, AN;
	SA = pathLoad[A];
	SB = pathLoad[B];
	Init();
	Dijkstra(A);

	AB = pathLoad[B];
	AN = pathLoad[N];
	Init();
	Dijkstra(B);
	BN = pathLoad[N];

	if (check == false) {
		cout << -1;
		return 0;
	}
	int minNum = min(SA + AB + BN, SB + AB + AN);
	cout << minNum;


}