글 읽기 - 외판원 - 틀렸습니다

kkweon 5년 전 0

게시판에 있는 예제들은 되서 어디가 잘못됬는지 못찾겠습니다 도와주세요 ㅜㅜ

#include <bits/stdc++.h>
using namespace std;

#define INF 1000001

/** has visited `city` ? */
bool has_visited(int visited, int city) { return (visited & (1 << city)) != 0; }
/** has visited all cities (e.g., n = 4 -> visited == b'1111' )? */
bool has_visited_all(int visited, int n) { return visited == (1 << n) - 1; }

int visit(int visited, int city) { return (visited | 1 << city); }

/**
 * @param visited - bitset represents visited cities
 * @param city - the last city to visit
 
 * @param cost - cost[i][j] returns the cost from i to j 
                 (e.g., cost[i][j] = 5)
                 
 * @param dp - dp[visited][city] cache 
               (e.g., dp[b'1111'][0] = 35)
 *
 * @return
 * the min cost of visting city as a last node
 */
int tsp(int visited,
        int city,
        const vector<vector<int>>& cost,
        vector<vector<int>>& dp) {
  int n = cost.size();

  if (has_visited_all(visited, n)) return cost[city][0] ? cost[city][0] : INF;

  int& ret = dp[visited][city];
  if (ret != -1) return ret;

  ret = INF;

  for (int i = 0; i < n; ++i) {
    if (!has_visited(visited, i) && cost[city][i]) {
      ret = min(ret, tsp(visit(visited, i), i, cost, dp) + cost[city][i]);
    }
  }

  return ret;
}

int main(int argc, char* argv[]) {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  int N;
  cin >> N;

  vector<vector<int>> cost(N, vector<int>(N, 0));
  vector<vector<int>> dp((1 << N), vector<int>(N, -1));

  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < N; ++j) {
      cin >> cost[i][j];
    }
  }

  cout << tsp(1, 0, cost, dp) << '\n';

  return 0;
}

yoonsang9114 5년 전 1

INF가 작네요. 10^9정도로 바꿔주면 AC를 받게 됩니다.

kkweon 5년 전 0

정말 감사합니다ㅜㅜ

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

문제

문제

출처

ICPC

외판원 - 틀렸습니다

kkweon 5년 전 0

yoonsang9114 5년 전 1

kkweon 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말