글 읽기 - [C++] 33%에서 틀렸습니다가 나옵니다.

so4644009 4년 전 0

과거에 도착할 수 있으면 possible, 아니면 not possible을 출력한다고 해서 음의 사이클을 찾은 후 cycle이 true이면 possible을, 아니면 not possible을 출력하도록 하였습니다. 반례가 있을까요?

#include <stdio.h>
#include <utility>
#include <vector>
#define MAX 1010
#define INF 2*1e9
using namespace std;

vector<pair<int,int>> v[MAX];
int dist[MAX];
bool cycle;
int n;

void bellman_ford(void){
    size_t i,j;
    fill(dist,dist+n,INF);
    dist[0]=0;
    cycle=0;
    for(i=0;i<n;++i)
        for(j=0;j<n;++j)
            for(auto chk:v[j])
                if(dist[j]!=INF&&dist[chk.first]>chk.second+dist[j]){
                    if(i==n-1) cycle=1;
                    dist[chk.first]=dist[j]+chk.second;
                }
    return;
}

int main(void){
    size_t i,j;
    int T;
    int m,a,b,c;
    scanf("%d",&T);
    for(i=1;i<=T;++i){
        scanf("%d %d",&n,&m);
        for(j=0;j<n;++j) v[j].clear();
        while(m--){
            scanf("%d %d %d",&a,&b,&c);
            v[a].push_back(make_pair(b,c));
        }
        bellman_ford();
        printf("Case #%d: %s\n",i,cycle?"possible":"not possible");
    }
    return 0;
}

so4644009 4년 전 0

사용하지 않은 조건 때문에 틀렸었고, 지금은 다시 풀어 해결했습니다.

minjoonist 4년 전 0

어떤 부분이 틀린 거였나요?

so4644009 4년 전 1

4번째 조건(

For some unknown reasons, starting from Ledang Mountain in Malaysia, it is always possible to end up in any mountain (of course, which also has Ledang Pool end point)on earth by hopping a sequence of Ledang Pools.

)이었던 걸로 기억합니다. 이 조건 때문에 역방향 그래프도 만들어야했던 걸로 기억합니다. 몇 달 전에 푼 문제여서 확실한지는 모르겠네요ㅠㅠ

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

문제

문제

출처

ICPC

[C++] 33%에서 틀렸습니다가 나옵니다.

so4644009 4년 전 0

so4644009 4년 전 0

minjoonist 4년 전 0

so4644009 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말