특정한 최단 경로 1504

문제

접근 방법

1->v1->v2->N
1->v2->v1->N
2가지 경우가 존재한다.
1->v1, v1->N의 경우는 v1을 기준으로 최단 거리를 구하면 찾을 수 있고
1->v2, v2->N의 경우도 마찬가지로 v2를 기준으로 하면 된다.
v1->v2, v2->v1은 방향성이 없는 그래프이기에 동일한 값이다.
다익스트라를 활용해 주면 된다.

코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
typedef pair<int, int> pii;
vector<vector<pii>> graph;
vector<int> dist;
int N, E;
void dijkstra(int start)
{
    fill(dist.begin(), dist.end(), 1e06);
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push({0, start});
    while (!pq.empty())
    {
        pii cur = pq.top();
        pq.pop();
        if (dist[cur.second] != 1e06)
            continue;
        dist[cur.second] = cur.first;
        for (pii next : graph[cur.second])
        {
            if (dist[next.second] != 1e06)
                continue;
            pq.push({cur.first + next.first, next.second});
        }
    }
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    int a, b, c, v1, v2, ret1 = 0, ret2 = 0;
    cin >> N >> E;
    graph = vector<vector<pii>>(N + 1, vector<pii>());
    dist = vector<int>(N + 1);
    while (E--)
    {
        cin >> a >> b >> c;
        graph[a].push_back({c, b});
        graph[b].push_back({c, a});
    }
    cin >> v1 >> v2;
    dijkstra(v1);
    if (dist[v2] == 1e06 || dist[N] == 1e06 || dist[1] == 1e06)
    {
        cout << -1;
        return 0;
    }
    ret1 += dist[v2] + dist[1];
    ret2 += dist[v2] + dist[N];
    dijkstra(v2);
    ret1 += dist[N];
    ret2 += dist[1];
    cout << min(ret1, ret2);
    return 0;
}

풀이

처음 제출할 땐 다익스트라 3번을 하였다.
(시작에서 1번, 두 지점에서 한 번씩)
하지만 굳이 그럴 필요 없이 두 번 하고 필요한 값을 취하면 됐다.

경로가 존재하지 않는 경우는 한번 다익스트라를 돌리고 각 지점에 도착했는지 확인해 보면 된다. (초깃값으로 설정됐다면 도착 못 한 것이다)

해당하는 부분과 관련하여 시작 지점과 무조건 연결되지 않았을 거로 생각했는데 막상 해당하는 부분을 체크하지 않아도 통과했다.

그래서 일단은 데이터 추가 요청을 해봤다.