백준 17835. 면접보는 승범이네 (C++)

요약

Dijkstra

문제

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

풀이

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int nodecnt, edgecnt, cnt;


struct Node {
    int to;
    long long cost;
};
vector<Node>Edge[100001];
bool operator<(Node A, Node B) {
    if (A.cost > B.cost) return true;
    else return false;
}
vector<int>room;
long long dist[100001] = { 0, };
priority_queue<Node>pq;


void init() {
    cin >> nodecnt >> edgecnt >> cnt;
    for (int i = 0; i < edgecnt; i++) {
        int now, to;
        long long cost;
        cin >> now >> to >> cost;
        Edge[to].push_back({ now, cost });
    }

    for (int i = 1; i <= nodecnt; i++) dist[i] = 1e18;

    for (int i = 0; i < cnt; i++) {
        int num;
        cin >> num;
        room.push_back(num);
        pq.push({ num, 0 });
        dist[num] = 0;
    }
}

void dijkstra() {

    while (!pq.empty()) {

        int now = pq.top().to;
        long long nowDist = pq.top().cost;
        pq.pop();
        if (nowDist > dist[now]) continue;
       
        for (int i = 0; i < Edge[now].size(); i++) {
            int next = Edge[now][i].to;
            long long cost = Edge[now][i].cost;
            long long nextDist = cost + nowDist;

            if (nextDist >= dist[next]) continue;
            dist[next] = nextDist;
            pq.push({ next, nextDist });
        }
    }

}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    init();
    dijkstra();

    long long ansDist = -1;
    int ansIdx = 1;
    for (int i = 1; i <= nodecnt; i++) {
        if (dist[i] > ansDist) {
            ansDist = dist[i];
            ansIdx = i;
        }
    }

    cout << ansIdx << '\n' << ansDist;
    
    return 0;
}

오류 발생 풀이

일단 기존 Dijkstra 처럼 모든 노드에 대해서 도착지까지 전부 최단 거리를 확인할 경우 무조건 시간 초과가 난다.
질문 게시판에 뭐가 없어서 혼자 어떻게든 최적화를 해보기 위해 맞는지는 모르겠지만 이런 시도를 해봤다. 결론은 전부 안됨.. ㅋ
1. checking 배열을 이용해서 면접장이 거기 있으면 continue
2. dist 배열을 최댓값으로 초기화 해주는 시간을 줄이기 위해 visited를 S로 갱신하며 현재 출발 노드에서 방문한 적 있을 때만 최단거리를 갱신하게 해봄
3. dp라는 이차원 배열에 [row : 해당 인덱스에서 면접장까지 갈 수 있는 최단거리] / [col : 해당 인덱스에서 가장 가까운 면접장 정보]를 기록해서 dp[now][0] 이 있을 경우, visited[dp[now][1]] 을 S로 방문했다는 처리를 해주고 (이걸 안해주면 room벡터를 돌며 확인하는 과정에서 방문한 기록이 없어서 전부 통과된다) 거리를 현재까지의 거리 + dp[now][0] 과 비교해서 갱신해봤다.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int nodecnt, edgecnt, cnt;
long long dist[100001] = { 0, };
int checking[100001] = { 0, };
int visited[100001] = { 0, };


struct Node {
    int to;
    long long cost;
};
vector<Node>Edge[100001];
bool operator<(Node A, Node B) {
    if (A.cost > B.cost) return true;
    else return false;
}
vector<int>room;

struct city {
    int num;
    long long distance;
};
long long dp[100001][2] = {0,};     // row : 최소거리, col : 가장 가까운 미팅룸
bool operator<(city A, city B) {
    if (A.distance < B.distance) return true;
    else if (A.distance > B.distance) return false;
    else if (A.num > B.num) return true;
    else return false;
}
priority_queue<city>ans;

void init() {
    cin >> nodecnt >> edgecnt >> cnt;
    for (int i = 0; i < edgecnt; i++) {
        int now, to;
        long long cost;
        cin >> now >> to >> cost;
        Edge[now].push_back({ to, cost });
    }
    for (int i = 0; i < cnt; i++) {
        int num;
        cin >> num;
        checking[num] = 1;
        room.push_back(num);
    }
}

void dijkstra(int S) {

    dist[S] = 0;
    visited[S] = S;

    long long min_toroom = 1e18;
    priority_queue<Node>pq;
    pq.push({ S,0 });
    while (!pq.empty()) {

        int now = pq.top().to;
        long long nowDist = pq.top().cost;
        pq.pop();
        if (nowDist >= min_toroom) continue;
        if (dp[now][0]) {
            if (nowDist + dp[now][0] < min_toroom) {
                min_toroom = nowDist + dp[now][0];
                visited[dp[now][1]] = S;
                continue;
            }
        }

        for (int i = 0; i < Edge[now].size(); i++) {
            int next = Edge[now][i].to;
            long long cost = Edge[now][i].cost;
            long long nextDist = cost + nowDist;

            if (dist[next] <= nextDist && visited[next] == S) continue;
            if (nextDist >= min_toroom) continue;   // 면접장까지의 최소 거리보다 크면 해볼필요도 없다.
            dist[next] = nextDist;
            visited[next] = S;
            if (checking[next] == 1) {
                min_toroom = nextDist;
                continue;
            }
            pq.push({ next, nextDist });
        }
    }

    long long minDist = 1e18;
    int num = -1;
    for (int i = 0; i < room.size(); i++) {
        if (visited[room[i]] != S) continue;
        if (dist[room[i]] < minDist) {
            minDist = dist[room[i]];
            num = room[i];
        }
    }
    ans.push({ S, minDist });
    dp[S][0] = minDist;
    dp[S][1] = num;
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    init();

    for (int i = 1; i <= nodecnt; i++) {
        if (checking[i] == 1) continue;
        dijkstra(i);
    }

    if (ans.empty()) cout << 1 << '\n' << 0;
    else {
        city answer = ans.top();
        int ansIdx = answer.num;
        long long ansDist = answer.distance;
        cout << ansIdx << '\n' << ansDist;
    }
    
    return 0;
}

질문게시판부터 보고 문제를 풀지 말지 정해야할듯 뭔가계속안되니까멘탈이털려버림 근데이제이게일상인 ㅋ ㅜㅠ