3번의 다익스트라 (O(3*ElogV)) or 플로이드-워셜 (O(V^3)) - 특정한 최단 경로

다익스트라 시간 복잡도: O(E*logV)
플로이드 워셜 시간 복잡도: O(V^3)
(E: 간선의 수, V: 노드의 수)

백준 특정한 최단 경로: https://www.acmicpc.net/problem/1504

방향성이 없는 그래프임을 주의!

int a, b, cost;
cin >> a >> b >> cost;
map[a].push_back({b, cost});
map[b].push_back({a, cost});	// 양방향 가능.

#define INF를 잡을 때,
1) INT_MAX로 한다면 덧셈 과정에서 int형 범위를 넘어갈 여지가 다분 => 특정 변수 long long으로 선언
2) 특정 변수에 따라 long long으로 선언하는 것이 귀찮다면 1e9(1e9+1e9여도 int형 범위를 넘기지 않음) 또는 문제에서 주어진 cost의 최댓값+1 설정

참고

// main
vector<pair<int, int>> arr[800+1];

// 위 배열을 받는 함수의 매게변수 선언
long long solution(vector<pair<int, int>>(&arr)[800 + 1], int n ....) {}

풀이

(1) 다익스트라를 3번 돌린다. => 3*O(nlogn)
- start node: 1
- start node: mid1
- start node: mid2

// 4개의 최단거리 테이블
	int d_start[800 + 1];			
	int d_mid1[800 + 1];
	int d_mid2[800 + 1];

	dijkstra(arr, d_start, n, 1);
	dijkstra(arr, d_mid1, n, mid1);
	dijkstra(arr, d_mid2, n, mid2);

(2) 경우의 수 2개
- start => mid1 => mid2 => n
- start => mid2 => mid1 => n

	long long case1 = (long long)d_start[mid1] + (long long)d_mid1[mid2] + (long long)d_mid2[n];
	long long case2 = (long long)d_start[mid2] + (long long)d_mid2[mid1] + (long long)d_mid1[n];

	if (case1 >= INT_MAX && case2 >= INT_MAX)
		return -1;
	else
		return min(case1, case2);

플로이드 워셜

노드(도시)의 갯수가 최대 800이라 간당간당했지만 O(n^3) 시간복잡도를 가진 플로이드 워셜 solution으로 풀리긴 했음

#include <bits/stdc++.h>
#define MAX_LEN 1000+1	// MAX_LEN을 INT_MAX(int형 최대로 두는 것과는 차이가 분명있다. long long으로 형변환이 필요하다.)
using namespace std;



// 플로이드 워셜 알고리즘을 통한 solution
int floyd(vector<pair<int, int>> (&arr)[800 + 1], int n, int mid1, int mid2) {
	
	// 이차원의 d 배열 생성
	vector<vector<int>> d(n + 1, vector<int>(n + 1, MAX_LEN));

	// 자기 자신과의 거리는 0으로 설정
	for (int i = 1; i <= n; i++) {
		d[i][i] = 0;
	}

	// 간선 정보 추가
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < arr[i].size(); j++) {
			// 기준 노드 i
			// arr[i][j].first: 연결노드 , arr[i][j].second: cost
			int linkedNode = arr[i][j].first;
			int cost = arr[i][j].second;

			d[i][linkedNode] = cost;
		}
	}

	// 플로이드-워셜 알고리즘
	for (int k = 1; k <= n; k++) {
		for (int s = 1; s <= n; s++) {
			for (int e = 1; e <= n; e++) {
				d[s][e] = min(d[s][e], d[s][k] + d[k][e]);
			}
		}
	}

	// 결과 
	int case1 = d[1][mid1] + d[mid1][mid2] + d[mid2][n];
	int case2 = d[1][mid2] + d[mid2][mid1] + d[mid1][n];

	if (case1 >= 1000 && case2 >= 1000)
		return -1;
	else
		return min(case1, case2);
}


// 다익스트라
void dijkstra(vector<pair<int, int>> (&arr)[800+1], int *d, int n, int start) {
	
	// <다익스트라>
	// 0. 최단거리 테이블 초기화
	for (int i = 1; i <= n; i++) {
		d[i] = INT_MAX;
	}

	// 1. 우선순위 큐 생성 + 처음 노드 삽입 and a[start] = 0;
	priority_queue<pair<int, int>> pq;
					// {cost, nodeNum}
	pq.push({ 0, start });
	d[start] = 0;

	// 2. while(!pq.empty()){...}
	while (!pq.empty()) {
		pair<int, int> now = pq.top(); pq.pop();
		// 현재 노드 번호
		int nowNodeNum = now.second;
		// 현재 노드까지 거리
		long long nowLength = -now.first;

		// 2-1. 현재 노드가 이전에 방문된 적이 있다면 무시
		if (d[nowNodeNum] < nowLength)
			continue;

		// 현재 노드와 인적해 있는 노드 모두 검색
		for (int i = 0; i < arr[nowNodeNum].size(); i++) {
			// 다음 노드가 현재 노드를 거쳐가는 것이 더 빠르다면, 
			pair<int, int> nextNode = arr[nowNodeNum][i];
			int nextCost = nowLength + nextNode.second;

			if (d[nextNode.first] > nextCost) {
				d[nextNode.first] = nextCost;
				pq.push({ -nextCost, nextNode.first });	// pq에서 push, pop에서 cost는 '-'를 붙여주어야 최단
			}
		}
	}



}

long long solution(vector<pair<int, int>>(&arr)[800 + 1], int n, int e, int mid1, int mid2) {
	/*
	경우의 수1) 1 => mid1 => mid2 => n
	경우의 수2) 1 => mid2 => mid1 => n
	두 경우의 수 중 더 짧은 경로 선z`택

	// 결국 3번의 다익스트라 필요
	*/


	// 4개의 최단거리 테이블
	int d_start[800 + 1];			
	int d_mid1[800 + 1];
	int d_mid2[800 + 1];

	dijkstra(arr, d_start, n, 1);
	dijkstra(arr, d_mid1, n, mid1);
	dijkstra(arr, d_mid2, n, mid2);

	long long case1 = (long long)d_start[mid1] + (long long)d_mid1[mid2] + (long long)d_mid2[n];
	long long case2 = (long long)d_start[mid2] + (long long)d_mid2[mid1] + (long long)d_mid1[n];

	if (case1 >= INT_MAX && case2 >= INT_MAX)
		return -1;
	else
		return min(case1, case2);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int n, e;
	cin >> n >> e;

	vector<pair<int, int>> arr[800+1];
	/*
	vector<int> arr(n);	<= 하나의 벡터안 요소의 갯수 n개로 지정
	vector<int> arr[n]: <= n개의 벡터(벡터 배열)
	*/


	for (int i = 0; i < e; i++) {
		int s, e, cost;
		cin >> s >> e >> cost;
		arr[s].push_back({ e, cost });
		arr[e].push_back({ s, cost });
	}

	int mid1, mid2;
	cin >> mid1 >> mid2;

	// 방법(1) 3번의 다익스트라 => 3*O(nlogn)
	//long long result = solution(arr, n, e, mid1, mid2);

	// 방법(2) 플로이드 워셜 => O(n^3)
	int result = floyd(arr, n, mid1, mid2);
	cout << result << '\n';
}