[백준]달빛 여우(16118)

문제 링크 : [백준]달빛 여우(16118)

문제 설명

달빛 여우와 달빛 늑대가 각자 1번 노드에서 모든 노드로 이동하는 최단 거리 중, 달빛 여우가 달빛 늑대보다 먼저 도착할 수 있는 노드가 몇개인지 구하세요.

1. 달빛 여우는 모든 거리를 동일한 속도로 이동합니다.
2. 달빛 늑대는 처음 이동하는 노드는 달빛 여우보다 두배 빠르게 이동합니다.
3. 달빛 늑대는 빠르게 이동한 후, 다음 이동은 달빛 여우보다 두배 느리게 이동합니다.
4. 달빛 늑대가 두배 느리게 이동한 후에는 다시 달빛 여우보다 두배 빠르게 이동합니다.
5. 달빛 늑대는 2, 3, 4를 반복하여 이동합니다.

입력

N(노드 갯수, 2 <= N <= 4,000)
M(엣지의 갯수, 1 <= M <= 100,000)
A_i B_i D_i(시작 지점, 도착 지점, 엣지의 길이, 1 <= D_i <= 100,000)

5 6
1 2 3
1 3 2
2 3 2
2 4 4
3 5 4
4 5 3

출력

1

카테고리

#다익스트라

시간 복잡도 상한

O(N * logN) 혹은 O(M * logM)

해결 방법

1. 각각 1번 노드에서 출발하여 모든 노드로 이동하는 최단거리를 구하여 비교하면 됩니다.
2. 그러나 달빛 늑대의 이동 방법이 일반적이지 않습니다.
3. 우선순위 큐에 넣을 데이터에 달빛 늑대의 상태를 저장합니다.
   3-1. 상태가 0인 경우 : 다음 이동 때 달빛 여우보다 두배 빠르게 이동
   3-2. 상태가 1인 경우 : 다음 이동 때 달빛 여우보다 두배 느리게 이동
4. 우선순위 큐에서 데이터를 꺼내, 다음 노드로 이동하는 데이터를 넣을 때, 현재 꺼낸 상태를 보고 다음 노드까지의 이동 시간을 계산합니다.
5. 나누기 2가 있기 때문에 소수가 발생하게 됩니다. 그러나 정밀도 등의 문제로 가급적 정수형을 쓰는게 좋습니다.
6. 처음에 거리를 입력 받을 때 곱하기 2만 해주어도 소수가 발생하지 않습니다.

시간복잡도

O(M * logM)

코드

#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
#define f first
#define s second
using namespace std;
typedef pair<int,int>P;
typedef long long L;
typedef pair<L,pair<int,int>>PI;
int n,m,a,b,c,i;
L d[4001],e[4001][2],g[4001];
vector<P>v[4001];
priority_queue<PI,vector<PI>,greater<PI>>q;
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m;
    while(m--){
        cin>>a>>b>>c;
        v[a].push_back({c*2,b});
        v[b].push_back({c*2,a});
    }
    q.push({0,{1,0}});
    while(!q.empty()){
        PI x=q.top();q.pop();
        if(d[x.s.f])continue;
        d[x.s.f]=x.f;
        for(P y:v[x.s.f]){
            if(d[y.s])continue;
            q.push({x.f+y.f,{y.s,0}});
        }
    }
    q.push({0,{1,0}});
    while(!q.empty()){
        PI x=q.top();q.pop();
        if(e[x.s.f][x.s.s])continue;
        e[x.s.f][x.s.s]=x.f;
        if(g[x.s.f])g[x.s.f]=min(g[x.s.f],x.f);
        else g[x.s.f]=x.f;
        for(P y:v[x.s.f]){
            if(e[y.s][!x.s.s])continue;
            int cc=x.s.s?y.f*2:y.f/2;
            q.push({x.f+cc,{y.s,!x.s.s}});
        }
    }
    for(a=0,i=2;i<=n;i++)a+=d[i]<g[i];
    cout<<a;
}