[백준 1504] 특정한 최단 경로 (C++)

문제 링크: https://www.acmicpc.net/problem/1504

1504번: 특정한 최단 경로

1. 주의할 점

- 최소 3번의 다익스트라 알고리즘을 사용해야 한다

- 반드시 지나야 하는점으로 시작점, 도착점 형태로 들어올 수 있다

 

2. 구현

- 모든 간선을 벡터에 저장한다

- Dijkstra 알고리즘을 3번 사용하기 위해 Visit배열은 False, Dist배열은 MAX로 초기화한다

- 시작점, 반드시 지나야 하는 2점에서 시작해 모든 Node까지의 최단거리를 우선순위를 사용한 다익스트라 알고리즘을 통해 구한다

- 시작점 -> Idx1 -> Idx2 -> N번째 Node까지 거리와 시작점 -> Idx2 -> Idx1 -> N번째 Node까지 거리의 최솟값을 Result에 저장하며, 만약 Result>=MAX인 경우 특정 최단 경로가 존재하지 않으므로 Result= -1로 초기화 한다

 

#define MAX 500000000
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
struct info {
	int idx, val;
};
struct cmp {
	bool operator()(info &a, info &b) {
		return a.val > b.val;
	}
};
info tmp;
int node, edge, s, e, val;
vector<info> v[801];
bool visit[3][801];
int dist[3][801];
vector<int> start;

void dijkstra() {
	for (int k = 0; k < 3; k++) {
		for (int i = 0; i <= node; i++) {
			visit[k][i] = false;
			dist[k][i] = MAX;
		}
	}
	for (int k = 0; k < 3; k++) {
		priority_queue<info, vector<info>, cmp> pq;
		dist[k][start[k]] = 0;
		tmp.idx = start[k];
		tmp.val = 0;
		pq.push(tmp);
		while (!pq.empty()) {
			int cidx = pq.top().idx;
			int cv = pq.top().val;
			pq.pop();
			if (visit[k][cidx]) continue;
			visit[k][cidx] = true;
			for (int i = 0; i < v[cidx].size(); i++) {
				int next = v[cidx][i].idx;
				int nv = v[cidx][i].val;
				if (dist[k][next] > cv + nv) {
					dist[k][next] = cv + nv;
					tmp.idx = next;
					tmp.val = cv + nv;
					pq.push(tmp);
				}
			}
		}
	}
}

int main() {
	cin.tie(NULL); cout.tie(NULL);
	ios::sync_with_stdio(false);
	cin >> node >> edge;
	for (int i = 0; i < edge; i++) {
		cin >> s >> e >> val;
		tmp.idx = e;
		tmp.val = val;
		v[s].push_back(tmp);
		tmp.idx = s;
		v[e].push_back(tmp);
	}
	int idx1,idx2;
	cin >> idx1 >> idx2;
	start.push_back(1);
	start.push_back(idx1);
	start.push_back(idx2);
	dijkstra();
	int result = min(dist[0][start[1]] + dist[1][start[2]] + dist[2][node],
		dist[0][start[2]] + dist[2][start[1]] + dist[1][node]);
	if (result >= MAX) result = -1;
	cout << result;
	system("pause");
	return 0;
}