P2910 [USACO08OPEN]Clear And Present Danger S——FLoyd-Warshell算法N^3解题

本是古典何须时尚 2023-01-21 11:19 109阅读 0赞

# 题目链接[https://www.luogu.com.cn/problem/P2910][https_www.luogu.com.cn_problem_P2910] #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center]

**题目描述**  
Farmer John is on a boat seeking fabled treasure on one of the N (1 <= N <= 100) islands conveniently labeled 1…N in the Cowribbean Sea.

The treasure map tells him that he must travel through a certain sequence A\_1, A\_2, …, A\_M of M (2 <= M <= 10,000) islands, starting on island 1 and ending on island N before the treasure will appear to him. He can visit these and other islands out of order and even more than once, but his trip must include the A\_i sequence in the order specified by the map.

FJ wants to avoid pirates and knows the pirate-danger rating (0 <= danger <= 100,000) between each pair of islands. The total danger rating of his mission is the sum of the danger ratings of all the paths he traverses.

Help Farmer John find the least dangerous route to the treasure that satisfies the treasure map’s requirement.

**输入格式**

*  Line 1: Two space-separated integers: N and M
 *  Lines 2…M+1: Line i+1 describes the i\_th island FJ must visit with a single integer: A\_i
 *  Lines M+2…N+M+1: Line i+M+1 contains N space-separated integers that are the respective danger rating of the path between island i and islands 1, 2, …, and N, respectively. The ith integer is always zero.

**输出格式**

*  Line 1: The minimum danger that Farmer John can encounter while obtaining the treasure.

**题意翻译**  
农夫约翰正驾驶一条小艇在牛勒比海上航行．

海上有  N ( 1 ≤ N ≤ 100 ) N(1\\leq N\\leq 100) N(1≤N≤100) 个岛屿，用  1 1 1 到  N N N 编号．约翰从  1 1 1 号小岛出发，最后到达  N N N 号小岛．

一张藏宝图上说，如果他的路程上经过的小岛依次出现了  A 1 , A 2 , … , A M ( 2 ≤ M ≤ 10000 ) A\_1,A\_2,\\dots ,A\_M(2\\leq M\\leq 10000) A1,A2,…,AM(2≤M≤10000)这样的序列（不一定相邻），那他最终就能找到古老的宝藏． 但是，由于牛勒比海有海盗出没．约翰知道任意两个岛屿之间的航线上海盗出没的概率，他用一个危险指数  D i , j ( 0 ≤ D i , j ≤ 100000 ) D D\_\{i,j\}(0\\leq D\_\{i,j\}\\leq 100000)D Di,j(0≤Di,j≤100000)D来描述．他希望他的寻宝活动经过的航线危险指数之和最小．那么，在找到宝藏的前提下，这个最小的危险指数是多少呢？

**输入输出格式**

**输入格式：**

第一行：两个用空格隔开的正整数 N 和 M。

第二到第 M+1 行：第 i+1 行用一个整数 Ai  
  
表示 FJ 必须经过的第 i 个岛屿

第 M+2 到第 N+M+1 行：第 i+M+1 行包含 N 个用空格隔开的非负整数分别表示 i 号小岛到第  1 … N 1\\dots N 1…N 号小岛的航线各自的危险指数。保证第 i 个数是 0。

**输出格式** 第一行：FJ 在找到宝藏的前提下经过的航线的危险指数之和的最小值。

**说明** 这组数据中有三个岛屿，藏宝图要求 FJ 按顺序经过四个岛屿：1 号岛屿、2 号岛屿、回到 1 号岛屿、最后到 3 号岛屿。每条航线的危险指数也给出了：航路(1,2),(2,3),(3,1) 和它们的反向路径的危险指数分别是 5,2,15,2,1。

FJ 可以通过依次经过 1,3,2,3,1,3号岛屿以 7 的最小总危险指数获得宝藏。这条道路满足了奶牛地图的要求 (1,2,1,3)。我们避开了 1 号和 2 号岛屿之间的航线，因为它的危险指数太大了。

注意：测试数据中 a 到 b 的危险指数不一定等于 b 到 a 的危险指数！

Translated by @LJC00125

**输入输出样例**  
输入 \#1复制

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

输出

**说明/提示**  
There are 3 islands and the treasure map requires Farmer John to visit a sequence of 4 islands in order: island 1, island 2, island 1 again, and finally island 3. The danger ratings of the paths are given: the paths (1, 2); (2, 3); (3, 1) and the reverse paths have danger ratings of 5, 2, and 1, respectively.

He can get the treasure with a total danger of 7 by traveling in the sequence of islands 1, 3, 2, 3, 1, and 3. The cow map’s requirement (1, 2, 1, and 3) is satisfied by this route. We avoid the path between islands 1 and 2 because it has a large danger rating.

**输入输出格式**

**输入格式：**

第一行：两个用空格隔开的正整数N和M

第二到第M+1行：第i+1行用一个整数Ai表示FJ必须经过的第i个岛屿

第M+2到第N+M+1行：第i+M+1行包含N个用空格隔开的非负整数分别表示i号小岛到第1…N号小岛的航线各自的危险指数。保证第i个数是0。

**输出格式**

第一行：FJ在找到宝藏的前提下经过的航线的危险指数之和的最小值。

**说明**

这组数据中有三个岛屿，藏宝图要求FJ按顺序经过四个岛屿：1号岛屿、2号岛屿、回到1号岛屿、最后到3号岛屿。每条航线的危险指数也给出了：航路(1，2)、(2，3)、(3，1)和它们的反向路径的危险指数分别是5、2、1。

FJ可以通过依次经过1、3、2、3、1、3号岛屿以7的最小总危险指数获得宝藏。这条道路满足了奶牛地图的要求（1，2，1，3）。我们避开了1号和2号岛屿之间的航线，因为它的危险指数太大了。

注意：测试数据中a到b的危险指数不一定等于b到a的危险指数！

————————————————————————

解题！

这道题的N小于等于200，于是O(n3)是可行的，又因为是最短路径问题，我们直接使用、最简单、最容易理解、最短、最暴力、只有五行的Floyd-Warshell算法。

Floyd算法思想：Floyd是一种动态规划的算法。三层循环，第一层循环中间点k，第二第三层循环起点终点i、j  
算法思想：如果点i到点k的距离加上点k到点j的距离小于原先点i的点j的距离，那么就用这个更短的路径长度来更新原先点i到点j的距离。

正解：

#include <iostream>
    
    using namespace std;
    
    #define inf 0xffffff
    
    int map[210][210];
    
    int main()
    { 
        int n, m;
        cin >> n >> m;
        int *dist = new int[m + 10];
        for (int i = 1; i <= m; i++)
            cin >> dist[i];
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
            { 
                cin >> map[i][j];
            }
        // Floyd核心算法
        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]); // Floyd动态规划更新操作
        // cout << "D2" << endl;
        int ans = 0;
        for (int i = 2; i <= m; i++)
        { 
            ans = ans + map[dist[i - 1]][dist[i]]; // 累加要求路径中的最短路径
            // 两个点之间的最短路径已经确认了，所以加的时候已经考虑到了间接节点
        }
        ans += map[1][dist[1]]; // 处理首尾节点
        ans += map[dist[m]][n];
        cout << ans << endl; // 输出
        // cout << "D3" << endl;
        return 0;
    }

[https_www.luogu.com.cn_problem_P2910]: https://www.luogu.com.cn/problem/P2910
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221020/41c948b2a6e94a5f961e4b57acb8c269.png