코드 복사/붙여넣기 하는 당신이 아름답습니다.

16118 : 달빛 여우

풀이

다익스트라 짜면서 사람들이 많이 놓치는 부분이 있는데

if (dp[now] != current_sum) continue;

위와 같은 동작을 넣은 코드와 그렇지 않은 코드의 시간복잡도가 다르다. (자세히는 모름)

이 문제의 경우, 데이터가 엄청 빡세서 저 동작을 넣어주지 않으면 시간 초과를 받게 된다.

아래의 코드를 참고하자.

코드

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

typedef long long ll;

int n, m;
struct edg {
    int idx, cnt;
    ll dst;
    bool operator <(edg a)const {
        return dst > a.dst;
    }
};
vector<edg> gph[100001];

void go(vector<ll> dp[], int f) {
    priority_queue<edg> pq;
    dp[0].resize(n+1); dp[1].resize(n+1);
    for (int i = 0; i <= n; i++) dp[0][i] = dp[1][i] = 1e17;

    pq.push({ 1,0,0 });
    dp[0][1] = 0;
    while (!pq.empty()) {
        edg now = pq.top(); pq.pop();
        int c = now.cnt;
        if (dp[c][now.idx] != now.dst) continue;
        for (int i = 0; i < gph[now.idx].size(); i++) {
            edg nxt = gph[now.idx][i];
            ll *x = &dp[f?(c+1)%2:c][nxt.idx], y = dp[c][now.idx], z = nxt.dst;
            z = f?c?z*2:z/2:z;
            if (*x > y + z) {
                *x = y + z;
                pq.push({ nxt.idx,f?(c+1)%2:c,*x });
            }
        }
    }
}

int main() {
    scanf("%d %d", &n, &m);
    while (m--) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        gph[u].push_back({ v,0,w*2 });
        gph[v].push_back({ u,0,w*2 });
    }

    vector<ll> r1[2], r2[2];
    go(r1, 0); go(r2, 1);

    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (r1[0][i] < min(r2[0][i], r2[1][i])) ans++;
    }

    printf("%d ", ans);

    return 0;
}

아무말

백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2018-09-14 18:08

Read more posts by this author