1504번-특정한 최단 경로

문제

https://www.acmicpc.net/problem/1504

1504번: 특정한 최단 경로

---

접근방법

1) 접근 사고

 

2) 시간 복잡도

 

3) 배운 점

 

4) PS

---

정답 코드

#include<bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define pii pair<int,int>
#define mp(X,Y) make_pair(X,Y)
#define mt(X,Y) make_tuple(X,Y)
#define mtt(X,Y,Z) make_tuple(X,Y,Z)
#define ll long long
#define sz(v) (int)(v).size()
 
using namespace std;
const int MAX = 801;
const int INF = 987654321;
vector<pair<int,int>> edge[MAX];
int n, e;
int main(void)
{
    fastio;
 
    cin >> n >> e;
 
    auto dijkstra = [&](int start) -> vector<int>{
        priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
        pq.push({0, start});
        vector<int> dist(n + 1, INF);
        dist[start] = 0;
 
        while(!pq.empty())
        {
            int cur = pq.top().second;
            int cost = pq.top().first;
            pq.pop();
 
            if(dist[cur] < cost)
                continue;
            for(auto idx : edge[cur])
            {
                int neighbor = idx.second;
                int neighborCost = idx.first + cost;
                if(dist[neighbor] > neighborCost)
                {
                    dist[neighbor] = neighborCost;
                    pq.push({neighborCost, neighbor });
                }
            }
        }
        return dist;
    };
 
    for(int i = 0; i < e; i++)
    {
        int s, f, c;
        cin >> s >> f >> c;
        edge[s].push_back({c, f});
        edge[f].push_back({c, s});
    }
    int node1, node2;
    cin >> node1 >> node2;
 
    /*
    1 -> 첫 번째 경유지 -> 두 번째 경유지 -> 도착지
    1 -> 두 번째 경유지 -> 첫 번째 경유지 -> 도착지
    중 더 작은 값이 경유지를 거쳐 도착지로 가는 최단 거리 배열이다
    */
    
    //1번 출발지에서 n번 지역으로가는 최단거리가 저장된 배열
    vector<int> stArr = dijkstra(1);
    //첫 번째 경유지에서 n번 지역으로가는 최단거리가 저장된 배열
    vector<int> nodeArr1 = dijkstra(node1);
    //두 번째 경유지에서 n번 지역으로가는 최단거리가 저장된 배열
    vector<int> nodeArr2 = dijkstra(node2);
    int ret = min(stArr[node1] + nodeArr1[node2] + nodeArr2[n], stArr[node2] + nodeArr2[node1] + nodeArr1[n]);
    if(ret >= INF || ret < 0)
        cout << -1<< "\n";
    else
        cout << ret <<"\n";
    return 0;
}