BOJ. Traveling Salesman problem (2098)

On this page

Problem: BOJ 2098 — Traveling Salesman Problem · 한국어 · 日本語

Bitmask dynamic programming

Fix city 0 as the starting city; every tour can be rotated to start there. Represent a state as (current, visited), where visited is a bitmask of the cities already visited and includes city 0. Let dp[current][visited] be the minimum additional cost needed to visit every remaining city exactly once and then return to city 0.

If every city has been visited, the remaining cost is the edge from current back to 0. If that directed edge does not exist, the state is impossible. Otherwise, try each unvisited city next for which the edge current → next exists, and take the minimum of the edge cost plus the corresponding subproblem:

dp[current][visited] = min(cost[current][next] + dp[next][visited | (1 << next)]).

The minimum is over valid next cities only. An input cost of zero means there is no edge, so such transitions must be skipped. If no complete tour exists, BOJ 2098 requires output 0; an impossible state is represented internally by INF and is never added to another cost.

There are N · 2^N states and each examines at most N next cities, so the time complexity is O(N² 2^N) and the space complexity is O(N 2^N). long costs and Long.MAX_VALUE / 4 as INF leave ample room for adding any valid route cost without overflow.

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    private static final long INF = Long.MAX_VALUE / 4;
    private static int n;
    private static int[][] cost;
    private static long[][] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(input.readLine().trim());
        cost = new int[n][n];
        for (int from = 0; from < n; from++) {
            String[] row = input.readLine().trim().split("\\s+");
            for (int to = 0; to < n; to++) {
                cost[from][to] = Integer.parseInt(row[to]);
            }
        }

        dp = new long[n][1 << n];
        for (long[] row : dp) {
            Arrays.fill(row, -1);
        }

        long answer = visit(0, 1);
        System.out.println(answer == INF ? 0 : answer);
    }

    private static long visit(int current, int visited) {
        if (visited == (1 << n) - 1) {
            return cost[current][0] == 0 ? INF : cost[current][0];
        }
        if (dp[current][visited] != -1) {
            return dp[current][visited];
        }

        long best = INF;
        for (int next = 0; next < n; next++) {
            int bit = 1 << next;
            if ((visited & bit) != 0 || cost[current][next] == 0) {
                continue;
            }

            long remaining = visit(next, visited | bit);
            if (remaining != INF) {
                best = Math.min(best, cost[current][next] + remaining);
            }
        }
        return dp[current][visited] = best;
    }
}