题目:

有 n 个景点，从一个景点 i 旅行到另一个景点 j 要花费 A=A(n≤100)，现在给出由 m(≤1e5) 个景点的组成序列 A，求：在所有 "有子序列 A 的序列中"，总花费最小的序列的花费为多少。

输入格式

第 1 行: 两个数，n 和 m。

第 2∼m+1行：第 i+1 行表示给定的序列中第 i 个景点 A。

第 m+2∼n+m+1 行：每行 n 个整数，表示景点之间的花费，自己到自己的花费一定是 0。

输出格式

共一行，输出满足条件的序列中最小花费为多少。

数据范围

对于 30%的数据, n≤10,m≤10

对于 50%的数据, m≤100

对于 100% 的数据, 0≤n≤100,0≤m≤100000,0≤A≤1000

Sample Input

Sample Output

题解：

求给定序列的最短路径。

根据贪心的思想，从A序列的第一个点出发，每到下一个点的路径都为最短路径，那整体将有最短路径。

Floyd算法的复杂度为O(n^3)可一次性求出所有点到其他点的最短路径。

使用Floyd算法本题复杂度为O(n^3+m) 根据本体数据，可行

Floyd算法是运用了dp思想

求点i到点j的距离能否通过k点进行优化，即map[i][j] = min(map[i][j], map[i][k] + map[k][j]);

从第一个点开始扩展，判断所有点能不能通过这个点进行优化，能就更新路径，一直到第n个点；

从而得出最短路径

（Floyd算法一定要使用邻接矩阵，而且不能链接的点要去无穷大值（相对大的值就好），因为复杂度较大使用时要注意数据大小）

Floyd算法：

 for(int k=1;k<=n;k++)//这个k一定要在最前面

        for(int i=1;i<=n;i++)

            for (int j = 1; j <= n; j++)

                map[i][j] = min(map[i][j], map[i][k] + map[k][j]);

AC代码：

#include<iostream>

#include<algorithm>

#define min(a,b){((a)<(b))?(a):(b)}

using namespace std;

typedef long long ll;

int s[100005];

int map[105][105];

int main() {

#if 1

    freopen("travel.in", "r", stdin);

    freopen("travel.out", "w", stdout);

#endif

    int n, m;

    ll ans = 0;

    cin >> n >> m;

    for (int i = 0; i < m; i++) {

        cin >> s[i];

    }

    for (int i = 1; i <= n; i++)

        for (int j = 1; j <= n; j++)

            cin >> map[i][j];

    for(int k=1;k<=n;k++)

        for(int i=1;i<=n;i++)

            for (int j = 1; j <= n; j++)

                map[i][j] = min(map[i][j], map[i][k] + map[k][j]);

    for (int i = 0; i < m-1; i++)

        ans += map[s[i]][s[i + 1]];

    printf("%d\n", ans);

    return 0;

}

Floyd算法

【Floyd算法+贪心】 travel 计蒜客 - 45275

题目:

题解：

AC代码：