https://programmers.co.kr/learn/courses/30/lessons/72413
문제 풀이모든 간선의 weight가 음수가 아닌 값, 시작점 s에서 도착할 수 있는 거리의 최소 비용을 구하는 문제라 다익스트라를 이용해 문제를 해결할 수 있다.
시작점 s에서 시작해 x점까지 같이 이동하는 최소 비용 + x점에서 시작해 a점까지 이동하는 최소 비용 + x점에서 시작해 b점까지 이동하는 최소 비용 중에서 가장 값이 작은 값을 찾는 문제다.원리는 간단하지만 다익스트라에 대해 잘 알고 있어야 풀 수 있는 문제다.
void dijkstra(int node) { for (int i = 1; i < 220; i++) { dist[node][i] = INF; } priority_queue<pair<int, int>> pq; pq.push(make_pair(0, node)); dist[node][node] = 0; while (!pq.empty()) { int nodeDist = -pq.top().first; int cntNode = pq.top().second; pq.pop(); if (dist[node][cntNode] != nodeDist) { continue; } for (pair<int, int> vertex : graph[cntNode]) { int nextWeight = nodeDist + vertex.second; int nextNode = vertex.first; if (nextWeight < dist[node][nextNode]) { dist[node][nextNode] = nextWeight; pq.push(make_pair(-nextWeight, nextNode)); } } }}
전체 소스 코드#include <bits/stdc++.h>using namespace std;const int INF = 987654321;long long dist[220][220];vector<vector<pair<int, int>>> graph;void dijkstra(int node) { for (int i = 1; i < 220; i++) { dist[node][i] = INF; } priority_queue<pair<int, int>> pq; pq.push(make_pair(0, node)); dist[node][node] = 0; while (!pq.empty()) { int nodeDist = -pq.top().first; int cntNode = pq.top().second; pq.pop(); if (dist[node][cntNode] != nodeDist) { continue; } for (pair<int, int> vertex : graph[cntNode]) { int nextWeight = nodeDist + vertex.second; int nextNode = vertex.first; if (nextWeight < dist[node][nextNode]) { dist[node][nextNode] = nextWeight; pq.push(make_pair(-nextWeight, nextNode)); } } }}int solution(int n, int s, int a, int b, vector<vector<int>> fares) { int answer = 0; graph = vector<vector<pair<int, int>>>(n + 1); for (vector<int> fare : fares) { int start = fare[0]; int end = fare[1]; int weight = fare[2]; graph[start].push_back(make_pair(end, weight)); graph[end].push_back(make_pair(start, weight)); } // dijkstra_start(s); for (int i = 1; i <= n; i++) { dijkstra(i); } long long minValue = INF; for (int i = 1; i <= n; i++) { if (minValue > dist[s][i] + dist[i][a] + dist[i][b]) { minValue = dist[s][i] + dist[i][a] + dist[i][b]; } } answer = minValue; return answer;}