글 읽기 - 반례좀 부탁드립니다ㅠㅠ

ekdud7667 4년 전 0

거리가 0이면 불가능이랑, 거리가 100만이 들어오는 경우를 대비해 min값을 충분히 크게 잡았습니다.

또 시간 제약을 피하기 위해서 permutation을 구할때 첫자리도 고정시켰습니다.

반례도 질문에서 찾아봤는데 어디가 잘못된건지 모르겠습니다ㅠㅠ

도와주세요..

#10971 외판원 순회2
# city=int(input())

from itertools import permutations
city=int(input())
distance=[list(map(int,input().split())) for _ in range(city)]
# 시간 단축을 위해 [1,2,3,4]중 앞의 1을 고정하고 [2,3,4]만 순열을 만들었습니다.
candidate= permutations([i+1 for i in range(1,city)])
min_value=1e9

for can_list in candidate:
  #[1]번 도시와 permutation의 첫번째 도시간의 거리
  candidate_value=abs(distance[0][can_list[0]-1])
  for j in range(city-1):
    # 마지막-> 처음 도시(1번도시)로 되돌아 오는 경우
    if j==city-2:
      city_distance= abs(distance[can_list[-1]-1][0])
    # 나머지 경우
    else:
      city_distance= abs(distance[can_list[j]-1][can_list[j+1]-1])
    # 거리가 0이면 불가능
    if city_distance==0:
      candidate_value=1e9
      break
    else:
      candidate_value+=city_distance

  min_value=min(min_value, candidate_value)
print(min_value)

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

문제

문제

출처

ICPC

반례좀 부탁드립니다ㅠㅠ

ekdud7667 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말