11088: 【原1088】邮递员小F

题目

题目描述

author: wcy 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1088

Description

因为制造类专业很难在大城市立足，曾经立志振兴中华之工业的小F，果断在本科毕业后转行做了一名光荣的邮递员。

他的任务是每天从总局出发，行走于所管辖区域的若干的邮局，收集所有的信，然后再汇总返回总局。

因为工作繁忙，同一个邮局他每天只希望去一次。

来往于任意两个邮局是有一定代价的。而且为了方便统计，假定来回两条道路上的代价假设是一样的。

现在小F希望你能给出他每天的最优行走方案，使得总的代价最少。

Input Format

输入数据包括两部分。

第一行为邮局数N。

接下来的N行为一个N×N的对称矩阵。矩阵的第i行，第j列元素Aij代表从邮局i到邮局j的消耗的代价。

规定总局的标号为1。

\( 1 \leq N \leq 15 \)

\( 0 \leq Aij \leq 2000 \)

Output Format

共一行，为满足题目要求的最小的代价。

Sample Input

Sample Output

BugenZhao's solution

//
// Created by BugenZhao on 2019/5/17.
//

#include <iostream>
#include <string>

using std::ios, std::cin, std::cout, std::endl, std::string;

unsigned N;
int d[15][15];
const int statusCount = 1U << 16U;
int dp[15][statusCount];

int getBit(unsigned num) {
    unsigned k = 1;
    int ans = 0;
    while (k <= 2 * num) {
        ans += (bool) (num & k);
        k <<= 1U;
    }
    return ans;
}

int getAns(int cur, unsigned status) {
    if (dp[cur][status] != -1) return dp[cur][status];
    if (getBit(status) == 2) {
        dp[cur][status] = d[0][cur];
        return dp[cur][status];
    }

    int ret = 0x7fffffff;
    for (unsigned i = 1; i < N; ++i) {
        if (i == cur) continue;
        if (status & (1U << i)) {
            int ans = getAns(i, status - (1U << cur)) + d[i][cur];
            if (ans < ret) ret = ans;
        }
    }
    dp[cur][status] = ret;
    return ret;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            cin >> d[i][j];
        }
    }

    if (N == 1) {
        cout << 0 << endl;
        return 0;
    }

    for (int i = 0; i < 15; ++i) {
        for (int j = 0; j < statusCount; ++j) {
            dp[i][j] = -1;
        }
    }

    int minAns = 0x7fffffff;
    dp[0][1] = 0;
    for (int i = 1; i < N; ++i) {
        int ans = d[0][i] + getAns(i, (1U << N) - 1);
        if (minAns > ans) minAns = ans;
    }
    cout << minAns << endl;
    return 0;

}

FineArtz's solution

/* 邮递员小F */
#include <iostream>
#include <cstring>
using namespace std;

const int INF = 2000000000;

int n;
int a[16][16];
int f[16][32768];

int main(){
    cin >> n;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            cin >> a[i][j];
    if (n == 1){
        cout << 0 << endl;
        return 0;
    }
    for (int i = 1; i <= (1 << n) - 1; i += 2){
        for (int j = 2; j <= n; ++j){
            if (i & (1 << (j - 1))){
                if (i ^ ((1 << (j - 1)) + 1)){
                    f[j][i] = INF;
                    for (int k = 2; k <= n; ++k){
                        if (k != j && i & (1 << (k - 1))){
                            f[j][i] = min(f[j][i], f[k][i ^ (1 << (j - 1))] + a[k][j]);
                        }
                    }
                }
                else
                    f[j][i] = a[1][j];
            }
        }
    }
    int ans = INF;
    for (int i = 2; i <= n; ++i){
        ans = min(ans, f[i][(1 << n) - 1] + a[i][1]);
    }
    cout << ans << endl;
    return 0;
}

ligongzzz's solution

#include <iostream>
using namespace std;

int map_data[20][20] = { 0 };

int mmin(int a, int b) {
    return a < b ? a : b;
}

bool visited[20] = { 0 };
int n;

int dfs(int pos, int m) {
    if (m == n - 1) {
        return map_data[pos][0];
    }
    visited[pos] = true;
    int ans = 999999999;
    for (int i = 0; i < n; ++i) {
        if (i != pos && !visited[i]) {
            auto cur_ans = dfs(i, m + 1) + map_data[pos][i];
            ans = cur_ans < ans ? cur_ans : ans;
        }
    }
    visited[pos] = false;
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n;

    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            cin >> map_data[i][j];

    /*
    for (int k = 0; k < n; ++k) {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                map_data[i][j] = mmin(map_data[i][j], map_data[i][k] + map_data[k][j]);
            }
        }
    }*/

    cout << dfs(0, 0);

    return 0;
}

yyong119's solution

#include <iostream>
using namespace std;
int n;
int map[16][16];
int cost;
bool flag[16];
 
void dfs(int depth, int temp, int pos) {
 
    if (temp >= cost) return;
    if (depth == n){
        if (temp + map[pos][1] < cost) cost = temp +map[pos][1];
        return;
    }
    for (int i = 2; i <= n; i++)
    if ((!flag[i])&&(i != pos)) {
        flag[i] = true;
        dfs(depth+1, temp + map[pos][i], i);
        flag[i] = false;
    }
}
int main() {
 
    cin>>n;
    cost = 2000 * 15;
 
    for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) {
        cin>>map[i][j];
    }
    dfs(1,0,1);
    cout<<cost;
}