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

题目:

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

输入格式 

第 $\mathrm{1 行:\; 两个数，n 和 m。}$

第 $\mathrm{2\sim m+1行：第 i+1 行表示给定的序列中第 i 个景点 Ai。}$

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

输出格式 

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

数据范围 

对于 $\mathrm{30\%的数据, n\le 10,m\le 10}$

对于 $\mathrm{50\%的数据, m\le 100}$

对于 $\mathrm{100\% 的数据, 0\le n\le 100,0\le m\le 100000,0\le Ai,j\le 1000}$

Sample Input

3 4
1
3
1
2
0 4 1
4 0 3
1 3 0

Sample Output

6

题解：

求给定序列的最短路径。

根据贪心的思想，从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;
}