개요

백준 1504: 특정한 최단 경로

• 입력
  첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존재하며, 그 거리가 c라는 뜻이다. (1 ≤ c ≤ 1,000) 다음 줄에는 반드시 거쳐야 하는 두 개의 서로 다른 정점 번호 v1과 v2가 주어진다. (v1 ≠ v2, v1 ≠ N, v2 ≠ 1) 임의의 두 정점 u와 v사이에는 간선이 최대 1개 존재한다.

• 출력
  첫째 줄에 두 개의 정점을 지나는 최단 경로의 길이를 출력한다. 그러한 경로가 없을 때에는 -1을 출력한다.

접근방식

1. 두 지점을 들렸다 가는 방식이기 때문에, 시작점이 세 곳일때의 다익스트라 알고리즘을 사용하는 단순한 방식을 썼다.

2. 시작점이 1번노드일때 최단거리 배열

   //시작노드부터 나머지 노드
   int minDistFirst[801];

   시작점이 첫번째 들려야할 노드일때 최단거리 배열

   //들려야할 노드 중 첫번째 노드부터 나머지 노드
   int minDistSecond[801];

   시작점이 두번째 들려야할 노드일때 최단거리 배열

   //들려야할 노드 중 두번째 노드부터 나머지 노드
   int minDistThird[801];

   세 가지 배열을 각자 다익스트라를 이용해 채워놓았다.
   

3. 들려야할 노드가 순서가 없다는 것을 신경을 못써서 처음 제출은 틀렸습니다 가 떴다.
   따라서 두가지 경로를 짠 다음 비교를 하는식으로 맞췄다.

   int tmpFirstWay = minDistFirst[firstLoc] + minDistSecond[SecondLoc] + minDistThird[N - 1];
    int tmpSecondWay = minDistFirst[SecondLoc] + minDistThird[firstLoc] + minDistSecond[N - 1];
   
   if (tmpFirstWay >= INF && tmpSecondWay >= INF) {
   		cout << -1;
   		return;
   }
   cout << min(tmpFirstWay,tmpSecondWay);

   두 경우 중 한 가지 경우의 루트만 n번 노드에 도달하지 못 할 수도 있으므로,
   두 경우의 길 둘다 INF값 이상이 나올때 -1을 출력하게 했다.

전체 코드

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

using namespace std;

vector<vector<pair<int, int>>> adj;

bool visited[801];
//시작노드부터 나머지 노드
int minDistFirst[801];
//들려야할 노드 중 첫번째 노드부터 나머지 노드
int minDistSecond[801];
//들려야할 노드 중 두번째 노드부터 나머지 노드
int minDistThird[801];

int INF = 1'600'001;

priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>> > pq;

int N, E, firstLoc,SecondLoc;

void Init() {
	fill(visited, visited + 801, false);
	while(!pq.empty())
	pq.pop();
}

void Input() {
	int tmpStart, tmpEnd, Dist;
	cin >> N >> E;
	adj.resize(N);
	for (int i = 0; i < E; i++) {
		cin >> tmpStart >> tmpEnd >> Dist;
		adj[--tmpStart].push_back({ --tmpEnd,Dist });
		adj[tmpEnd].push_back({ tmpStart,Dist });
	}
	cin >> firstLoc >> SecondLoc;
	firstLoc--;
	SecondLoc--;
	fill(minDistFirst, minDistFirst + 801, INF);
	fill(minDistSecond, minDistSecond + 801, INF);
	fill(minDistThird, minDistThird + 801, INF);
	Init();
}
void Solution() {
	//1번 노드에서 각 노드로의 다익스트라 알고리즘 적용하기
	minDistFirst[0] = 0;
	pq.push({ minDistFirst[0],0 });
	while (!pq.empty()) {
		int curNode = pq.top().second;
		pq.pop();

		while (!pq.empty() && visited[curNode]) {
			curNode = pq.top().second;
			pq.pop();
		}
		if (visited[curNode]) break;

		visited[curNode] = true;

		for (pair<int, int>& p : adj[curNode]) {
			int nextNode = p.first, nextDist = p.second;
			if (minDistFirst[nextNode] > minDistFirst[curNode] + nextDist) {
				minDistFirst[nextNode] = minDistFirst[curNode] + nextDist;
				pq.push({ minDistFirst[nextNode],nextNode });
			}
		}

	}
	Init();

	//firstLoc노드에서 나머지 노드로의 다익스트라 알고리즘 적용
	minDistSecond[firstLoc] = 0;
	pq.push({minDistSecond[firstLoc],firstLoc});

	while (!pq.empty()) {
		int curNode = pq.top().second;
		pq.pop();
		while (!pq.empty() && visited[curNode]) {
			curNode = pq.top().second;
			pq.pop();
		}

		if (visited[curNode]) break;

		visited[curNode] = true;
		for (pair<int, int>& p : adj[curNode]) {
			int nextNode = p.first, nextDist = p.second;
			if (minDistSecond[nextNode] > minDistSecond[curNode] + nextDist) {
				minDistSecond[nextNode] = minDistSecond[curNode] + nextDist;
				pq.push({ minDistSecond[nextNode],nextNode });
			}
		}
	}
	Init();
	//secondLoc에서 나머지 노드로의 다익스트라 알고리즘 적용
	minDistThird[SecondLoc] = 0;
	pq.push({minDistThird[SecondLoc],SecondLoc});

	while (!pq.empty()) {
		int curNode = pq.top().second;
		pq.pop();
		while (!pq.empty() && visited[curNode]) {
			curNode = pq.top().second;
			pq.pop();
		}

		if (visited[curNode]) break;

		visited[curNode] = true;

		for (pair<int, int>& p : adj[curNode]) {
			int nextNode = p.first, nextDist = p.second;
			if (minDistThird[nextNode] > minDistThird[curNode] + nextDist) {
				minDistThird[nextNode] = minDistThird[curNode] + nextDist;
				pq.push({minDistThird[nextNode],nextNode});
			}
		}
	}
	//firstLoc을 먼저 들리는 경우
	int tmpFirstWay = minDistFirst[firstLoc] + minDistSecond[SecondLoc] + minDistThird[N - 1];
	//secondLoc을 먼저 들리는 경우
	int tmpSecondWay = minDistFirst[SecondLoc] + minDistThird[firstLoc] + minDistSecond[N - 1];

	//두가지 경우의 길이 둘다 N번째 노드에 도달할 수 없다면
	if (tmpFirstWay >= INF && tmpSecondWay >= INF) {
		cout << -1;
		return;
	}
	//도달할 수 있다면 둘 중에 짧은 경로로 출력
	cout << min(tmpFirstWay,tmpSecondWay);
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	Input();
	Solution();
}

문풀후생

처음에 INF값을 도시 갯수* 각 최대 거리로 800'001으로 설정했는데
틀렸습니다가 떴다.
생각해보니 양방향 그래프이므로 각 거리를 한번 더 갈 수 있으므로,
최대거리를 1000이 아니라 2*1000으로 잡아야 한다.