[백준 2982] 국왕의 방문 (C++)

문제 링크: www.acmicpc.net/problem/2982

2982번: 국왕의 방문

1. 주의할 점

- 국왕의 현재 위치를 알고 있어야 한다 or 각 도로가 통제되는 시간을 알고 있어야 한다

- 조건에 맞게 구현을 정확히 해야한다

 

2. 구현

- 교차로의 수만큼 Dist[] 배열을 초기화한다

- 교황이 방문하는 교차로를 Loc 벡터에 담는다

- 모든 도로에 대한 정보를 V[] 벡터와 도로의 길이를 Road[][] 배열에 담는다

- rSum[] 배열에는 교황이 순서대로 방문하는 교차로까지 걸리는 시간을 담는다

- popeLoc(Sum) 함수를 통해 Sum시간일 때, 교황이 몇 번째 도로에 위치하는지 반환한다. 만약 순회가 끝난 경우, -1을 반환한다

- 우선순위큐를 이용한 다익스트라 알고리즘을 통해서 최단시간을 구한다

- popLoc() 함수를 통해 현재 교황이 순회중이라면 어떤 교차로 사이의 도로를 이용하고 있는지 Ka,Kb에 교차로 번호를 담는다. 만약 다음으로 이동하려는 도로가 현재 교황이 이용하고 있다면, 기다려야 하는 시간을 waitTime에 저장한다.

- waitTime은 교황이 현재 도로를 모두 순회하는 시간(rSum[pl]) - 현재 시간(CV)를 통해 구한다

- 다음 교차로까지 이동하는데 최단시간이 갱신된다면 이동하고, 아닌 경우에는 이동하지 않는다. 이때, 다음 교차로까지의 최단시간은 현재시간 + 대기시간 + 해당 도로에 소요되는 시간으로 계산한다

#define MAX 987654321
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
struct info{
    int idx,val;
};
struct cmp{
    bool operator()(info &a, info &b){
        return a.val > b.val;
    }
};
info tmp;
int node,edge,val,s,e,curTime=0,num,ka,kb,a,b,diff;
int dist[1001];
vector<int> loc;
vector<info> v[1001];
int road[1001][1001];
int rSum[1001];

int popeLoc(int sum){          //Sum시간일 때, 교황이 몇번째 도로에 위치해 있는지
    ka=-1;
    kb=-1;
    for(int i=0;i<loc.size()-1;i++){
        if(sum<=rSum[i]){
            ka=loc[i];
            kb=loc[i+1];
            return i;
        }
    }
    return -1;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin>>node>>edge>>s>>e>>diff>>num;
    for(int i=1;i<=node;i++)
        dist[i]=MAX;
    for(int i=0;i<num;i++){
        cin>>val;
        loc.push_back(val);
    }
    for(int i=0;i<edge;i++){
        cin>>a>>b>>val;
        v[a].push_back({b,val});
        v[b].push_back({a,val});
        road[a][b]=val;
        road[b][a]=val;
    }
    int sum=0;
    for(int i=0;i<loc.size()-1;i++){
        a = loc[i];
        b = loc[i+1];
        sum+=road[a][b];
        rSum[i]=sum;
    }
    priority_queue<info,vector<info>,cmp> pq;
    pq.push({s,diff});
    dist[s]=diff;
    while(!pq.empty()){
        int cidx = pq.top().idx;
        int cv = pq.top().val;
        pq.pop();
        if(dist[cidx]<cv) continue;
        if(cidx==e){
            cout<<cv-diff;
            break;
        }
        int pl = popeLoc(cv);
        for(int i=0;i<v[cidx].size();i++){
            int next = v[cidx][i].idx;
            int nv = v[cidx][i].val;
            int waitTime = 0;
            if((cidx==ka && next==kb) || (cidx==kb && next==ka))         //교황 순회중 + 해당 도로를 사용하려는 경우
                waitTime = rSum[pl]-cv;
            
            if(dist[next]>waitTime+cv+nv){
                dist[next]=waitTime+cv+nv;
                pq.push({next,waitTime+cv+nv});
            }
        }
    }
    return 0;
}