11060: 【原1060】小X的机器人

题目描述

author: 寿鹤鸣原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1060

Description

小X最近在实验室进行一项机器人实验，他有三个机器人，需要在一个广场上提供服务。如果某项服务请求发生在某处，如果该处没有机器人，一个机器人必须立刻移动到该处为其提供服务。但是小X的网络系统出现了一些问题，某个时刻只能让一个机器人移动。他们必须为了提供服务而移动，且两个机器人不能在某一时刻移动到同一位置。

将某个机器人从位置p移动到位置q需要C(p,q)的花费。C(p,q)不一定等于C(q,p), 但C(p,p)一定等于0。被机器人服务的位置顺序与服务请求的顺序相同。

现在小X找到了你，希望能安排机器人服务的顺序使得总费用最少。

Input Format

第一行有两个整数L和N, L(\(3 \leq L \leq 200\))是可能的请求位置的总数, N是总请求数. 位置用1, 2, ... , L表示.

接下来L行每行包含L个非负的整数，其中第(i+1)行的第j列个数表示从i到j的费用C(i, j), 满足\(C(i, j) \leq 2000\).

最后一行有N个整数，按顺序表示请求的位置。

初始时，三个机器人分别在1, 2, 3位置。

Output Format

输出仅一行，包含一个整数M, 表示最小的总费用。

Hint

Sample Input

5 9
0 1 1 1 1
1 0 2 3 2
1 1 0 4 1
2 1 5 0 1
4 2 3 4 0
4 2 4 1 5 4 3 2 1

Sample Output

FineArtz's solution

/* 小X的机器人 */
#include <iostream>
using namespace std;

const int INF = 0x7fffff;

int c[201][201];
int f1[201][201], f2[201][201];
int a[1005];

int minn(initializer_list<int> il){
    int ret = INF;
    for (int i : il)
        if (ret > i)
            ret = i;
    return ret;
}

int main(){
    int n, l;
    cin >> l >> n;
    for (int i = 1; i <= l; ++i)
        for (int j = 1; j <= l; ++j)
            cin >> c[i][j];
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    for (int j = 1; j <= l; ++j)
        for (int k = 1; k <= l; ++k)
            f1[j][k] = f2[j][k] = INF;
    f1[2][3] = f1[3][2] = 0;
    a[0] = 1;
    for (int i = 0; i < n; ++i){
        for (int j = 1; j <= l; ++j){
            for (int k = 1; k <= l; ++k){
                if (a[i] == j || a[i] == k || j == k)
                    continue;
                f2[j][k] = minn({f1[j][k] + c[a[i]][a[i + 1]], f2[j][k], INF});
                f2[a[i]][k] = minn({f1[j][k] + c[j][a[i + 1]], f2[a[i]][k], INF});
                f2[a[i]][j] = minn({f1[j][k] + c[k][a[i + 1]], f2[a[i]][j], INF});
            }
        }
        for (int j = 1; j <= l; ++j)
            for (int k = 1; k <= l; ++k){
                f1[j][k] = f2[j][k];
                f2[j][k] = INF;
            }
    }
    int ans = INF;
    for (int i = 1; i <= l; ++i)
        for (int j = 1; j <= l; ++j)
            if (ans > f1[i][j])
                ans = f1[i][j];
    cout << ans << endl;
    return 0;
}