글 읽기 - 비트 마스크 필수?

gshs340507 5년 전 0

이 코드에서 비트 마스크를 적용시키면 시간이 단축되나요?

느낌 상 시간차가 없을 것 같은데... 꼭 비트 마스크를 써야하는 건지 의문이 듭니다.

또한 외판원 순회 문제가 방향 그래프에서 MST 구하는 방법이라고 생각해도 되는지 궁금하네요..

#include <bits/stdc++.h>
#define MAX 20
#define INF 987654321

using namespace std;
typedef pair <int, int> pii;

vector <pii> graph[MAX]; // graph[v1].(v2, cost)
vector <bool> visit;
int vertax;
int ans = INF;

int minCost(int cst, int start, int current, int Vsize);

int main()
{
    scanf("%d", &vertax);
    visit.resize(vertax + 1, false);
    for(int i = 1; i <= vertax; i++){
        for(int j = 1; j <= vertax; j++){
            int cost;
            scanf("%d", &cost);
            if(cost != 0) graph[i].push_back(make_pair(j, cost));
        }
    }
    for(int i = 1; i <= vertax; i++){
        int M = minCost(0, i, i, 0);
        if(ans > M) ans = M;
    }
    printf("%d", ans);
}

int minCost(int cst, int start, int current, int Vsize)
{
    if(cst >= ans) return INF;
    int res = INF;
    if(Vsize == vertax){
        if(start != current) return INF;        
        return cst;
    }
    for(int i = 0; i < graph[current].size(); i++){
        pii there = graph[current][i];
        if(!visit[there.first]){
            visit[there.first] = true;
            res = min(res, minCost(cst + there.second, start, there.first, Vsize + 1));
            visit[there.first] = false;
        }    
    }
    return res;
}

startlink 5년 전 0

비트 마스크 안 써도 됩니다
MST랑 아무 관계가 없습니다.

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

문제

문제

출처

ICPC

비트 마스크 필수?

gshs340507 5년 전 0

startlink 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말