글 읽기 - 1162 도로 포장 53프로에서 계속 틀리는 이유

algobird 5년 전 0

다른 분들은 d[i][k]를 i번 정점이 향후 도착 정점까지 도로 포장을 할 수 있는 기회가 k번 남게 하는 경로들 중 최소를 저장하셨는데

저는 시작 정점에서 i번 정점까지 k번 도로 포장한 경로들 중 최소를 저장한 것 외에는 다른 부분이 없는 것 같은데 어디서 틀렸는지

못 찾겠습니다.. 범위 long long으로 했을 때도 53프로에서 틀렸었습니다 ㅠㅠ

#include <iostream>
#include <queue>
#include <stdio.h>
#define MAX 1<<30
using namespace std;

int d[10001][21]; //how many did I packaged
vector<pair<int,int> > m[10001];
priority_queue <pair<int,pair<int,int> > > pq; //weight,node,k
int V,E,K;

int main()
{
    cin>>V>>E>>K;

    for(int i=0;i<E;++i) {
        int u,v,w;
        cin>>u>>v>>w;

        m[u].push_back({v,w});
        m[v].push_back({u,w}); //push_back({a,0})?
    }

    for(int i=1;i<=V;++i) {
        for(int j=0;j<=K;++j) d[i][j]=MAX;
    }

    pq.push({0,{1,0} });
    d[1][0]=0;

    while(!pq.empty()) {
        int now=pq.top().second.first;
        int k=pq.top().second.second;
        int w1=-pq.top().first;

        pq.pop();

        if(d[now][k]<w1) continue; // < ?

        for(int i=0;i<m[now].size();++i) {
            int next=m[now][i].first;
            int w2=m[now][i].second;

            if(d[next][k]<w1+w2) continue; // <=? different with bfs

            d[next][k]=w1+w2;
            pq.push({-d[next][k],{next,k} });

            if(w2!=0 && k<K && d[next][k+1]>w1) { // >= ?
                d[next][k+1]=w1; //w2==0
                pq.push({-d[next][k+1],{next,k+1} });
            }
        }
    }

   /*
   for(int i=1;i<=V;++i) {
        for(int j=0;j<=K;++j) printf("%d ",d[i][j]);
        printf("\n");
    }
    */

    int ans=MAX; for(int i=0;i<=K;++i) { if(ans>d[V][i]) ans=d[V][i]; }

    printf("%d",ans);
    return 0;
}

djm03178 5년 전 1

일단 int로 하면 절대 맞을 수가 없습니다. long long으로 바꿨다고 하셨지만 바꾸는 과정에서 다른 것이 달라졌을 수도 있으니 가능하면 long long으로 틀렸던 버전을 올려주세요.

djm03178 5년 전 1

모두 long long으로 바꾸고 INF도 늘려주니 맞았습니다.

algobird 5년 전 0

와 진짜 감사합니다.. 어딘가를 제대로 안 바꿨던 것 같습니다

감사합니다!!!!!!!!!!!!

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

문제

문제

출처

ICPC

1162 도로 포장 53프로에서 계속 틀리는 이유

algobird 5년 전 0

djm03178 5년 전 1

djm03178 5년 전 1

algobird 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말