[백준 16118] 달빛 여우 (C++)

문제 링크: https://www.acmicpc.net/problem/16118

16118번: 달빛 여우

1. 주의할 점

- 늑대가 같은 지점에 최단 경로로 도착하는것보다 돌아서 가는게 빠를 수 있다(느릴 때, 빠를 때 적절히 이용)

- 1번째 Node까지의 최단시간을 0으로 설정하지 않는다(0을 이용하여 돌아갈 수 있다)

- d와 M의 범위가 크므로 Long Long을 이용한다

 

2. 구현

- Info 객체를 이용한 우선순위 큐를 사용하여 다익스트라 함수를 완성한다

- Dist[idx][flag] 배열을 통해 해당 idx번째 Node에 늑대가 짝수번에([][0]) 도착했는지, 홀수번에([][1]) 도착했는지 기록하고 여우는 [][2]에 기록한다

- 여우가 1초에 2만큼 이동한다고 가정하면, 늑대가 빠르게 이동할때 1초에 4만큼, 느릴때는 1만큼 이동한다. 이를 통해 Dist[][]에는 각 Node까지의 거리(거리 = 속력*시간)를 담는다

- V[] 벡터에는 오솔길에 대한 정보를 저장한다

- 우선순위큐와 구조체를 적절히 이용하여 다익스트라를 완성한다. 또한, 현재 늑대가 빠르게 이동하는지 느리게 이동하는지 계산하여 다음 Node까지의 거리를 계산한다

 

#define MAX 9876543210
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
struct info{
    int idx,odd;
    long long val;
};
struct cmp{
    bool operator()(info &a, info &b){
        return a.val > b.val;
    }
};
vector<info> v[4001];
int node,edge,a,b,result=0;
long long val;
long long dist[4001][3];       //[][0]: 늑대 짝, [][1]: 늑대 홀, [][2]: 여우

void dijkstra(int flag){
    priority_queue<info,vector<info>,cmp> pq;
    if(flag==0) pq.push({1,0,0});
    else pq.push({1,0,0});
    while(!pq.empty()){
        int cidx = pq.top().idx;
        int codd = pq.top().odd;
        long long cval = pq.top().val;
        pq.pop();
        if(dist[cidx][flag+codd]<cval) continue;
        for(int i=0;i<v[cidx].size();i++){
            int next = v[cidx][i].idx;
            
            long long nv = v[cidx][i].val;
            if(flag==0 && codd==1)  nv*=4;
            else if(flag==2) nv*=2;
            
            int nextOdd = 0;
            if(flag==0) nextOdd = codd==1 ? 0 : 1;
            if(dist[next][flag+nextOdd]>cval+nv){
                dist[next][flag+nextOdd]=cval+nv;
                pq.push({next,nextOdd,cval+nv});
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin>>node>>edge;
    //초기화
    for(int i=1;i<=node;i++)
        for(int j=0;j<4;j++)
            dist[i][j]=MAX;
    
    for(int i=0;i<edge;i++){
        cin>>a>>b>>val;
        v[a].push_back({b,0,val});
        v[b].push_back({a,0,val});
    }
    for(int i=0;i<4;i+=2)
        dijkstra(i);
    
    for(int i=2;i<=node;i++){
        long long wolfMin = min(dist[i][0], dist[i][1]);
        long long foxMin = dist[i][2];
        if(wolfMin>foxMin) result++;
    }
    cout<<result;
    return 0;
}