글 읽기 - 달빛 여우 문제 질문입니다.

mhkim4886 5년 전 0

접근법은, 다익스트라 알고리즘을 여우와 늑대에 대해 각각 돌립니다.

여우에 대해서는 평범하게 다익스트라를 돌리고(단 간선의 길이 v를 2배로 늘려서 합니다), 늑대에 대해서는 한 번은 거리를 v로, 한 번은 4v로 놓고 돌립니다.

그 결과를 비교해서 여우가 더 빨리 도착하는 경우를 셉니다.

대회 때부터(온사이트 참가자입니다) 고민했고, 대회 끝나고 나서 푼 사람들 말을 들어봐도 거의 저랑 비슷하게 접근한 거 같았는데 아무리 해도 2%에서 틀렸습니다 라고 뜨네요... 무슨 문제일까요 ㅠㅠㅠ

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
#include <bitset>
#include <queue>
using namespace std;
typedef long long lli;
typedef pair<int, int> pii;
typedef pair<lli, lli> pll;
vector<int> G[5000], V[5000];
bitset<5000> visited;
int visit[5000];
lli d1[5000];
pll d2[5000];
priority_queue<pll, vector<pll>, greater<pll>> pq1;
priority_queue<pll, vector<pll>, greater<pll>> pq2;

int main()
{
    // freopen("in.txt", "r", stdin);

    int n, m;
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= m; i++)
    {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        G[a].push_back(b);
        G[b].push_back(a);
        V[a].push_back(c);
        V[b].push_back(c);
    }

    int from = 1;
    for(int i = 1; i <= n; i++) d1[i] = 1e12;
    d1[from] = 0;
    int curr = from;
    // 여우에 대한 다익스트라
    while(true)
    {
        visited[curr] = true;
        for(int i = 0; i < G[curr].size(); i++)
        {
            int k = G[curr][i];
            int v = V[curr][i];
            d1[k] = min(d1[curr] + v*2, d1[k]);
            pq1.emplace(d1[k], k);
        }
        while(!pq1.empty() && visited[pq1.top().second]) pq1.pop();
        if(pq1.empty()) break;
        curr = pq1.top().second;
        pq1.pop();
    }

    from = 1;
    for(int i = 1; i <= n; i++) d2[i] = { 1e12, 1e12 };
    d2[from].second = 0;
    curr = from;
    visit[curr] = 0;
    pq2.emplace(1e12, curr);
    // 늑대에 대한 다익스트라
    while(!pq2.empty())
    {
        visit[curr]++;
        for(int i = 0; i < G[curr].size(); i++)
        {
            int k = G[curr][i];
            int v = V[curr][i];
            d2[k].first = min(d2[curr].second + v, d2[k].first);
            d2[k].second = min(d2[curr].first + v*4, d2[k].second);
            pq2.emplace(d2[k].first, k);
            pq2.emplace(d2[k].second, k);
        }
        while(!pq2.empty() && visit[pq2.top().second] == 2) pq2.pop();
        if(pq2.empty()) break;
        curr = pq2.top().second;
        pq2.pop();
    }

    int ans = 0;
    for(int i = 1; i <= n; i++)
    {
        // printf("%lld, %lld/%lld\n", d1[i], d2[i].first, d2[i].second);
        if(d1[i] < min(d2[i].first, d2[i].second)) ans++;
    }
    printf("%d", ans);
}

jwvg0425 5년 전 0

늑대의 두 가지 경우를 하나로 묶어서 방문하는 것 같은데, 제 생각에는 지금 빨리 가는 차례인지 / 느리게 가는 차례인지로 정점을 아예 2개로 분리를 해서 보는게 맞지 않을까 싶네요.

아래는 반례입니다.

4 4

1 2 1

2 3 10

2 4 1

4 1 1

답: 0

말씀하신 대로 짝수번째 방문/홀수번째 방문으로 정점을 둘로 나누어서 문제는 풀긴 했는데, 왜 제가 접근했던 방식대로 하면 반례가 존재할지 생각하다가 막혔습니다. Dijkstra 알고리즘에서는 우선순위 큐를 이용해서 아직 방문하지 않은 점 중 시작점으로부터의 거리가 가장 짧은 점을 방문하는 것을 방문하고 그때 그 점까지의 거리를 확정(= 이후에 바뀌지 않음)합니다.

그리고 이 문제에 대한 제 접근은 어떤 노드에 시작점으로부터 홀수 개의 간선을 지난 후, 시작점으로부터 짝수 개의 간선을 지난 후에 방문하는 2가지 경우를 pair로 관리하면서 원래의 다익스트라 알고리즘처럼 홀수번째 방문이든 짝수번째 방문이든 시작점에서 가까운 노드를 먼저 방문하도록 했습니다. 단 방문할 때 홀수/짝수 모두를 업데이트하도록 하고, 둘 모두를 확정하기 위해 각 노드마다 2번 방문하도록 했습니다(그래서 visit 배열이 2가 될 때 visited 처리되어 우선순위 큐에서 pop 처리).

이 풀이는 반례가 있으니 틀렸을 텐데, 왜 틀렸는지를 생각해봤지만 제 풀이가 맞다고도 주장 못하겠고 틀렸다고도 주장 못하겠습니다. 이 풀이는 왜 틀렸을까요? 즉 어떤 경우에 틀리는 풀이인가요?

jwvg0425 5년 전 1

풀이가 틀렸다기보단 구현 상의 미스가 있는 것 같습니다. 실제로 중단점을 걸고 돌려보시거나 로그를 찍어보시면 좀 알기 쉬울 것 같은데, 기존 최단거리랑 같은 값이 들어와도 공회전을 도는 부분에서 visited값이 올라가면 안 되는데 올라가서 서로 다른 두 경우를 모두 보지 못하는 경우가 생깁니다.

mhkim4886 5년 전 1

열심히 삽질하다 보니 맞았습니다! 공회전을 도는 부분을 "first, second 모두 업데이트되지 않는 경우" 로 놓고 공회전 2번을 도는 경우에 pq에서 pop 시키는 알고리즘으로 하니까 맞네요. 감사합니다:D

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

달빛 여우 문제 질문입니다.

mhkim4886 5년 전 0

jwvg0425 5년 전 0

mhkim4886 5년 전 1

mhkim4886 5년 전 0

jwvg0425 5년 전 1

mhkim4886 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말