백도어 17396

문제

접근 방법

다익스트라를 활용해서 풀면 된다.
하지만 상대방의 시야에 해당하는 분기점은 경유할 수 없으니 미리 빼놓거나 탐색 과정에서 제외해주면 된다.

코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
typedef pair<ll, int> pli;
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    int N, M, a, b, t;
    cin >> N >> M;
    priority_queue<pli, vector<pli>, greater<pli>> pq;
    vector<bool> blocked(N);
    vector<vector<pli>> graph(N, vector<pli>());
    vector<ll> dir(N, 10000000001);
    for (int i = 0, j; i < N; ++i)
    {
        cin >> j;
        blocked[i] = j;
    }
    for (int i = 0; i < M; ++i)
    {
        cin >> a >> b >> t;
        if ((blocked[a] && a < N - 1) || (blocked[b] && b < N - 1))
            continue;
        graph[a].push_back({t, b});
        graph[b].push_back({t, a});
    }
    dir[0] = 0;
    pq.push({0, 0});
    while (!pq.empty())
    {
        pli cur = pq.top();
        pq.pop();
        if (dir[cur.second] < cur.first)
            continue;

        for (pli next : graph[cur.second])
        {
            if (dir[next.second] <= dir[cur.second] + next.first)
                continue;
            dir[next.second] = dir[cur.second] + next.first;
            pq.push({dir[next.second], next.second});
        }
    }
    cout << (dir[N - 1] == 10000000001 ? -1 : dir[N - 1]);
    return 0;
}

풀이

분기점의 수 100,000, 걸리는 시간 100,000 총 100000 * 100000의 값이 나올 수 있다. 그러한 점을 유의해서 타입을 사용해야 한다.
다익스트라를 오랜만에 접해서 실수로 프림 알고리즘처럼 작성했다. (우선순위 큐에 거릿값이 아닌 간선의 값을 넣었다) 그래서 많이 틀렸다.