[백준 1504] 특정한 최단 경로

백준 1504 특정한 최단 경로

우선순위 큐를 이용한 다익스트라 공부중.....(소스가 좀 드러울 수도 있음)

(지금은 소스만 올리고 나중에 정리해서 수정할 예정)

#include<queue>
#include<vector>
#include<cstdio>
#include<algorithm>
 
using namespace std;
 
const long long INF = 98765432;
 
vector<vector<pair<int, int>>> map;
priority_queue<pair<int, int>> pq;
vector<long long> ans;
int v, e;
 
long long Daijk(int start, int end)
{
    ans.clear();
    ans.resize(v + 1);
    fill(ans.begin(), ans.end(), INF);
 
    pq.push(make_pair(0, start));
    ans[start] = 0;
 
    while (!pq.empty())
    {
        pair<int, int> now = pq.top(); pq.pop();
        int cost = -now.first;
        int here = now.second;
 
        for (int i = 0; i < map[here].size(); i++)
        {
            int next = map[here][i].first;
            int next_cost = map[here][i].second;
 
            if (ans[next] > ans[here] + next_cost)
            {
                ans[next] = ans[here] + next_cost;
                pq.push(make_pair(-next_cost, next));
            }
        }
    }
    
    return ans[end];
}
 
int main()
{
 
    scanf("%d %d", &v, &e);
    map.resize(v + 1);
 
    int from, to, cost;
    for (int i = 0; i < e; i++)
    {
        scanf("%d %d %d", &from, &to, &cost);
        map[from].push_back(make_pair(to, cost));
        map[to].push_back(make_pair(from, cost));
    }
    int start, end;
    scanf("%d %d", &start, &end);
 
    long long out1 = Daijk(1, start);
    long long out2 = Daijk(end, v);
    long long out3 = Daijk(1, end);
    long long out4 = Daijk(start, v);
    long long mid = Daijk(end, start);
 
    long long ans1, ans2;
    ans1 = out1 + out2;
    ans2 = out3 + out4;
 
    if (mid == INF || (ans1 >= INF && ans2 >= INF))return !printf("-1");
    return !printf("%d", (ans1 > ans2 ? ans2 : ans1) + mid);
}