문제 출처

1. 문제설명

  • N개의 정점과 M개의 간선으로 이뤄진 그래프가 있다.
  • 경유지 v1, v2가 주어진다.
  • 1번 정점에서 N번 정점으로 이동하는데, v1, v2를 반드시 거쳐야 한다.

  • 위 조건을 만족하는 최단 경로를 구하라

  • 문제 분류
    • Graph, Dijkstra


2. 알고리즘 설계

  • 다익스트라 문제이고, 이전 문제와 달리 두 개의 노드를 반드시 들려야 한다.
  • 우선 문제에서 방향성이 없는 그래프 라고 명시했으니, 입력 u, v에 대해 [u][v] = [v][u] 모두 저장해줘야 한다.
  • 이 문제의 경우 두 가지 경우의 수가 있을 것이다.
    • 1->a->b->N
    • 1->b->a->N
  • 두 가지 경로에 대한 다익스트라 값을 구해서 최소값을 취하면 된다.
  • 경로는 int 범위를 넘어설 수 있으니, long long을 취해야 한다.
  • 경로가 없는 경우 -1을 출력하라고 명시되어 있다.
    • 경로가 더해지면 INF 값이 두번 이상 더해질 수 있으니, ‘INF 값보다 크다면’으로 조건을 세워야 한다.


3. 전체 코드

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;

const int SZ = 802, INF = 0x3f3f3f3f;
int n, m, a, b;
vector<pii> adj[SZ];

long long solve(int src, int dst) {
	int D[SZ];
	fill(D, D+n+1, INF);

	priority_queue<pii, vector<pii>, greater<pii>> pq;
	pq.push({0, src});
	D[src] = 0;

	for(int u, v, w, dw; !pq.empty();) {
		tie(w, u) = pq.top();
		pq.pop();

		for(auto nxt : adj[u]) {
			tie(dw, v) = nxt;

			if(dw + w < D[v]) {
				D[v] = dw + w;
				pq.push({dw+w, v});
			}
		}
	}

	return D[dst];
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	for(int u, v, c; m--;) {
		cin >> u >> v >> c;
		adj[u].push_back({c, v});
		adj[v].push_back({c, u});
	}

	cin >> a >> b;
	long long tmp = min(solve(1,a) + solve(a,b) + solve(b,n), solve(1,b) + solve(b,a) + solve(a,n));
	cout << (tmp >= INF ? -1 : tmp);

	return 0;
}