백준) 16118 달빛 여우

다들 다익스트라를 배우고 이해는 한다.

아~ 계속 간선 길이를 늘려가면서 점마다 우선순위큐로 dp를 찍어주면 되는구나~

이해는 하고 기초 문제를 풀고 나면 다익스트라를 다 아는 것 같은 착각이 든다 ㅎㅎ

근데 이제 다익스트라를 조금만 꽈서 낸 문제면 풀질 못한다 ㅜㅜ

어느 알고리즘이나 응용이 어렵지만, 내가 느끼기엔 다익스트라가 유독 까다롭더라.

그래서 이제부터 좀 다양한 다익스트라 문제들을 올리려고 한다.

이 글을 호오오오옥시 읽는 분들도 아는 문제가 있으면 추천을 부탁드립니다.

---------------------------------------------------------------------------------------------------------------------------------------------------------------------

1) 백준 16118 달빛 여우

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

조금만 꽈서 낸 문젠데 세 번이나 틀리고 맞았다 ^^

여우의 경우 1번 정점부터 나머지 정점까지 최소경로의 길이는 순수 다익스트라로 구할 수 있다.

늑대의 경우 내가 현재 정점에 오기전에 2배 빠르게 왔는지, 느리게 왔는지 기억해야 한다.

그래서 나는 구현을 쉽게 할려고(정말?), 간선을 2배로 뿔렸다. 즉 2배 빨라지는 길, 2배 느려지는 길을 추가했다.

그러면 전에 빨라지는 길로 왔었다면, 이번엔 느려지는 길로만 갈 수 있게 된다.

dp(fox, wolf)에는 빠르게 왔는지, 느리게 왔는지를 둘 다 기록했다.

#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
 
typedef long long ll;
 
int n, m;
int a, b;
ll fox[4001], wolf[4001][2], c;
 
struct edge_f {
    int to;
    ll cost;
 
    bool operator< (const edge_f& e) const {
        return cost > e.cost;
    }
};
 
struct edge_w {
    int to;
    ll cost;
    bool fast; //길 종류
 
    bool operator< (const edge_w& e) const {
        return cost > e.cost;
    }
};
 
int main() {
    scanf("%d %d", &n, &m);
 
    vector<vector<edge_f>> vf(n + 1);
    vector<vector<edge_w>> vw(n + 1);
 
    for (int i = 0; i < m; ++i) {
        scanf("%d %d %lld", &a, &b, &c);
        vf[a].push_back({ b, 2ll * c });
        vf[b].push_back({ a, 2ll * c });
 
        vw[a].push_back({ b, c, false });
        vw[a].push_back({ b, 4ll * c, true });
        vw[b].push_back({ a, c, false });
        vw[b].push_back({ a, 4ll *c, true });
    }
 
    //////////////////////여우
    memset(fox, -1, sizeof(fox));
 
    priority_queue<edge_f> pqf;
    pqf.push({ 1, 0ll });
 
    while (!pqf.empty()) {
        edge_f e = pqf.top(); pqf.pop();
 
        if (fox[e.to] != -1) {
            continue;
        }
 
        fox[e.to] = e.cost;
 
        for (auto next : vf[e.to]) {
            if (fox[next.to] != -1) {
                continue;
            }
            pqf.push({ next.to, e.cost + next.cost });
        }
    }
    //////////////////////여우
 
    //////////////////////늑대
    memset(wolf, -1, sizeof(wolf));
 
    priority_queue<edge_w> pqw;
    pqw.push({ 1, 0ll, true });
 
    while (!pqw.empty()) {
        edge_w e = pqw.top(); pqw.pop();
 
        if (wolf[e.to][e.fast] != -1)
            continue;
 
        wolf[e.to][e.fast] = e.cost;
 
        for (auto next : vw[e.to]) {
            if (wolf[next.to][next.fast] != -1)
                continue;
            
            if (e.fast != next.fast) { //종류가 다른 길로 가야 해
                pqw.push({ next.to, e.cost + next.cost, next.fast });
            }
        }
    }
    //////////////////////늑대
 
    int ans = 0;
    ll _min, _max;
    for (int i = 1; i <= n; ++i) {
        _min = min(wolf[i][0], wolf[i][1]);
        _max = max(wolf[i][0], wolf[i][1]);
 
        if (_min == -1) { //못 가는 노드가 있을 경우
            if (fox[i] < _max) {
                ans++;
            }
        }
        else {
            if (fox[i] < _min) {
                ans++;
            }
        }
    }
 
    printf("%d", ans);
 
    return 0;
}

2) bitonic path

scpc 2차 예선 문제였는데 링크를 찾고 있습니다 ㅜ