글 읽기 - 이거 도대체 반례가 무엇일까요?

sohyeon24 6년 전 0

외판원 순회2 문제입니다.

채점 70%정도에 틀렸다고 나옵니다~ 어디가 틀렸는지 전혀 모르겠네요 ㅜㅜ

어디가 틀렸을까요? ㅜㅜ

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n); // 지나가는 도시의 순열
    int w[n][n];
    for(int i=0; i<n; i++){
        a[i] = i;
        for(int j=0; j<n; j++){
            cin >> w[i][j];
        }
    }
    int ans = 2147483647;
    do{
        int sum = 0;
        for(int i=0; i<n-1; i++){
            if(w[a[i]][a[i+1]] == 0) break;
            sum += w[a[i]][a[i+1]];
        }
        if(w[a[n-1]][a[0]] == 0) break;
        sum += w[a[n-1]][a[0]];
        ans = min(ans,sum);
    }while(next_permutation(a.begin(), a.end()));

    cout << ans << "\n";

    return 0;
}

yukariko 6년 전 0

이렇게 고치니 정답이네요.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n); // 지나가는 도시의 순열
    int w[n][n];
    for(int i=0; i<n; i++){
        a[i] = i;
        for(int j=0; j<n; j++){
            cin >> w[i][j];
        }
    }
    int ans = 2147483647;
    do{
        int sum = 0;
        bool find = false;
        for(int i=0; i<n-1; i++){
            if(w[a[i]][a[i+1]] == 0) find = true;
            sum += w[a[i]][a[i+1]];
        }
        if(find || w[a[n-1]][a[0]] == 0) continue;
        sum += w[a[n-1]][a[0]];
        ans = min(ans,sum);
    }while(next_permutation(a.begin(), a.end()));

    cout << ans << "\n";

    return 0;
}

jsy890908 6년 전 0

24번째줄에 break해버리면 do-while 문이 break되어 버리니 다음 으로 못가죠

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

문제

문제

출처

ICPC

이거 도대체 반례가 무엇일까요?

sohyeon24 6년 전 0

yukariko 6년 전 0

jsy890908 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말