글 읽기 - 10971 외판원 2 시간초과에요

justking 6년 전 0

시간초과 뜨는데 어디서 뜨는걸까요? ㅠ

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

int n;
int a[11][11];

int main(){
    scanf("%d",&n);
   
    for(int i=0;i<n;i++){
        for(int j = 0;j<n;j++){
            scanf("%d",&a[i][j]);
        }
    }
    
    vector<int> d(n);
    for(int i = 0; i < n; i++){
         d.push_back(i);
    }
    
    int ans = 1000000000;
    
    do{
        bool ok = true;
        int sum = 0;
        for(int i = 0;i < n-1; i++){
            if(a[d[i]][d[i+1]] == 0){
                ok = false;
            }else{
                sum += a[d[i]][d[i+1]];
            }
        }
        
        if(ok && a[d[n-1]][d[0]] != 0){
            sum += a[d[n-1]][d[0]];
            if(ans>sum){
                ans = sum;
            }
        }
    }while(next_permutation(d.begin()+1, d.end()));

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

seico75 6년 전 0

ok = false;

를

continue;

로 바꾸면 좀 빨라질 것 같습니다.

justking 6년 전 0

38번줄때문에 바꿀수가..ㄷㄷ

seico75 6년 전 0

for가 하나더 있네요 . ok false 뒤에 break를 넣어야할꺼 같고..

근본적으로 메모이제이션이 있어서 while 루프수가 줄어야할꺼 같습니다.

justking 6년 전 0

제가 소름돋는거발견했어요

22번줄

d.push_back(i); 이거를

d[i] = i; 로바꾸면 기적이 일어나네요

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

문제

문제

출처

ICPC

10971 외판원 2 시간초과에요

justking 6년 전 0

seico75 6년 전 0

justking 6년 전 0

seico75 6년 전 0

justking 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말