백준 17396 - 백도어(C++)

문제 링크입니다. https://www.acmicpc.net/problem/17396

17396번: 백도어

탐색 횟수가 많은 다익스트라 문제였습니다.

시작점에서 마지막점까지 갈 수 있는지를 확인하는 문제였습니다.

X번 정점을 갈 수 있는지 여부를 확인한 뒤, 이에 따라 최소 거리를 구해야합니다.

 

N <= 100,000, M <= 300,000 이기에 무작정 탐색을 하면 시간초과가 됩니다.

따라서 시간을 줄여주는 과정이 필요합니다.

 

1. 갈 수 없는 점에 대한 간선을 저장하지 않기

2. 같은 점을 여러번 탐색할 때, 저장된 최소거리보다 작으면 탐색하지 않기

 

위와 같은 방법을 통해 시간 초과를 피할 수 있었습니다.

 

위의 조건만 기억해주고, 간단한 다익스트라 알고리즘을 구현하면 풀 수 있는 문제입니다.

 

자세한 것은 코드를 참고해주세요.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
#define F first
#define S second
#define INF 1234987654321
#define LL long long int 
#define P pair<LL, int>

using namespace std;

int N, M;
int View[100001];
vector<P> connect[100001];
LL Distance[100001];
priority_queue<P> q;

void reset_distance(){
    for(int i = 1; i <= N; i++){
        Distance[i] = INF;
    }
}

void Dijstra(){
    Distance[1] = 0;
    q.push({-0, 1});
    while(!q.empty()){
        int x = q.top().S;
        LL cost = -q.top().F;
        q.pop();
        if(Distance[x] < cost) continue;
        for(int i = 0; i < connect[x].size(); i++){
            int xx = connect[x][i].F;
            int n_cost = connect[x][i].S;
            if(Distance[xx] > Distance[x] + n_cost){
                Distance[xx] = Distance[x] + n_cost;
                q.push({-Distance[xx], xx});
            }
        }
    }
}

void solve(){
    reset_distance();
    Dijstra();
    if(Distance[N] == INF) cout << "-1";
    else cout << Distance[N];
}

int main() {
    cin.tie(0);
    cout.tie(0);
    cin >> N >> M;
    for(int i = 1; i <= N; i++){
        cin >> View[i];
    }
    View[N] = 0;
    for(int i = 1; i <= M; i++){
        int x, y, cost;
        cin >> x >> y >> cost;
        if(View[x+1] == 1 || View[y+1] == 1) continue;
        connect[x+1].push_back({y+1, cost});
        connect[y+1].push_back({x+1, cost});
    }
    solve();
    return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요