글 읽기 - 틀리는 이유를 모르겠습니다. 알려주시면 감사하겠습니다 (C++)

give654 1년 전 0

그룹 i에서 그룹 j로 갈 수 있다고 할 때,

그룹 i의 정점 중 하나를 v라고 하고,

그룹 j의 정점들 중 v보다 작으면서 가장 큰 값을 가지는 정점을 a,

그룹 j의 정점들 중 v보다 크면서 가장 작은 값을 가지는 정점을 b라고 하면

v -> a / cost = abs(v - a)

v -> b / cost = abs(b - v)

이 2개의 간선을 이어준 뒤, 다익스트라를 돌리는 풀이입니다.

그런데, 왜 틀리는지 모르겠어서,

N이 좀 작은 반례를 주시거나, 풀이 지적해주시면 감사하겠습니다.

//#define LOCAL_TEST
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll, int>;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
#ifdef LOCAL_TEST
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    ll INF = 1e10;
    int N, K;
    int goal_id;
    cin >> N >> K;

    vector<int> get_id(N + 1);
    vector id(N + 1, vector<int>());
    vector<bool> visited(N + 1, false);
    vector adj(K + 1, vector<int>(K + 1));
    vector<ll> dist(N + 1, INF);
    priority_queue<P, vector<P>, greater<>> pq;

    for (int i = 1; i <= N; ++i){
        int bi;
        cin >> bi;
        get_id[i] = bi;
        id[bi].push_back(i);
        if (i == N)
            goal_id = bi;
    }

    for (int i = 1; i <= K; ++i)
        for (int j = 1; j <= K; ++j){
            char c;
            cin >> c;
            if (c == '1') adj[i][j] = 1;
            else adj[i][j] = 0;
        }

    dist[1] = 0;
    pq.push(P(0, 1));

    while (!pq.empty()){

        int curr;
        do{
            curr = pq.top().second;
            pq.pop();
        }while (!pq.empty() && visited[curr]);

        if (visited[curr]) break;
        visited[curr] = true;

        int curr_id = get_id[curr];
        if (adj[curr_id][goal_id] == 1){
            dist[N] = min(dist[N], dist[curr] + N - curr);
        }

        for (int i = 1; i <= K; ++i){
            if (adj[curr_id][i] == 1){
                auto iter = lower_bound(id[i].begin(), id[i].end(), curr);
                if (iter != id[i].end()){
//                    curr 보다 큰 원소들 중 curr와 가장 가까운 원소
                    int t = *iter;
                    if (dist[curr] + abs(t - curr) < dist[t]){
                        dist[t] = dist[curr] + abs(t - curr);
                        pq.emplace(dist[t], t);
                    }
                }
                else if (iter != id[i].begin()){
//                    curr 보다 작은 원소들 중 curr 와 가장 가까운 원소
                    iter--;
                    int t = *iter;
                    if (dist[curr] + abs(t - curr) < dist[t]){
                        dist[t] = dist[curr] + abs(t - curr);
                        pq.emplace(dist[t], t);
                    }
                }

            }
        }
    }

    if (dist[N] == INF) cout << -1 << endl;
    else cout << dist[N] << endl;
    return 0;
}

give654 1년 전 0

조건문 실수네요.. 해결했습니다..

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

문제

문제

출처

ICPC

틀리는 이유를 모르겠습니다. 알려주시면 감사하겠습니다 (C++)

give654 1년 전 0

give654 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말