글 읽기 - 어떤 논리가 틀렸는지를 모르겠습니다

mc_progw12 3년 전 0

다익스트라를 돌리면서 방문체크를 하지 않고 특정 노드에 K번째로 도착하는 경우의 비용이 K번째 최단경로이다

라고 생각하며 풀었더니 9%에서 가차 없이 틀려버리네요..

그리고 블로그에서는 힙을 노드의 개수만큼이나 선언해서 쓰던데,

다익스트라의 pq에서는 항상 비용이 가장 적은 것이 top으로 뽑히는데 굳이 힙이 필요한가요?

#include <bits/stdc++.h>
#define endl "\n"
#define ll long long
#define INF 1000000002
#define setting ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
using namespace std;






struct P{
    int x,c;
    inline bool operator<(const P &b) const{
        return c > b.c;
    }
};

int n,m,k;
int x,y,z;
vector<P> v[1001];
int vi[1001];
int ans[1001];
priority_queue<P> q;

int main()
{
    setting;
    cin >>n>>m>>k;
    while(m--){
        cin >>x>>y>>z;
        v[x].push_back({y,z});
    }

    q.push({1,0});
    while(!q.empty()){
        int qx = q.top().x;
        int qc = q.top().c;
        vi[qx]++; q.pop();

        if(vi[qx] == k) ans[qx] = qc;
        if(vi[qx] > k) continue;

        for(P i:v[qx]){
            if(vi[i.x] < k){
                q.push({i.x,qc+i.c});
            }
        }
    }

    for(int i=1;i<=n;i++){
        if(!ans[i]) cout << -1 << endl;
        else cout << ans[i] << endl;
    }
}

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

문제

문제

출처

ICPC

어떤 논리가 틀렸는지를 모르겠습니다

mc_progw12 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말