글 읽기 - 왜틀리는지 모르겠습니다 다익스트라 반례알려주실수있는분

sontg123 3년 전 0

별난리 다쳐도 안되서.. 스트레스 받는중입니다 ㅠㅠ

혹시나해서 INF 도 크게 해봤는데 소용이 없네요 일단 본문 테스트케이스는 잘 통과됩니다..

방법은 그냥 다익스트라에서 min_dis 테이블에 k크기의 벡터 만들고 다 inf로 채워넣은 뒤 작은 경로가 생기면 뒤로 밀면서 순서에 알맞은 칸에 채워넣는 방식입니다(lower bound) k-1번째가 inf라면 -1출력하고 있으면 그거 출력합니다

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define INF 1000000000000000000
using namespace std;
typedef long long ll;
struct compare{
    bool operator()(pair<int,ll>& a,pair<int,ll>& b){
        return a.second>b.second;
    }
};
class k_dijkstra{
private:
    vector<vector<pair<int,ll>>> path;
    vector<vector<ll>> dp;
    ll N,M,K;
public:
    k_dijkstra(){
        std::cin >> N >> M >> K;
        path.resize(N+1);
        dp.resize(N+1,vector<ll>(K,INF));
        set_val();
    }
    void set_val(){
        int a,b,dis;
        for(int i=0;i<M;i++){
            std::cin >> a >> b >> dis;
            path[a].push_back({b,dis});
        }
    }
    void dijkstra(){
        priority_queue<pair<int,ll>,vector<pair<int,ll>>,compare> pq;
        dp[1][0]=0;
        pq.push({1,0});
        pair<int,ll> cur,next;
        ll tmp;
        while(!pq.empty()){
            cur=pq.top();
            pq.pop();
            if(dp[cur.first][K-1]<cur.second)
                continue;
            for(int i=0;i<path[cur.first].size();i++){
                next=path[cur.first][i];
                tmp =cur.second+next.second;
                if(dp[next.first][K-1]>tmp){
                    int it =lower_bound(dp[next.first].begin(),dp[next.first].end(),tmp)-dp[next.first].begin();
                    for(int j=it;j<K-1;j++)
                        dp[next.first][j+1]=dp[next.first][j];
                    dp[next.first][it]=tmp;
                    pq.push({next.first,dp[next.first][it]});
                }
            }
        }
        for(int i=1;i<=N;i++){
            if(dp[i][K-1]==INF)
                std::cout << -1 <<'\n';
            else
                std::cout << dp[i][K-1]<<'\n';
        }
    }

};
int main(){
    k_dijkstra kd;
    kd.dijkstra();

    return 0;
}

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

문제

문제

출처

ICPC

왜틀리는지 모르겠습니다 다익스트라 반례알려주실수있는분

sontg123 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말