题解 P2910 【[USACO08OPEN]寻宝之路Clear And Present Danger】

说起来这还是本蒟蒻学完Floyd之后做的第一道题。

emm...这是一道裸题，题目大致是说有一堆岛，岛之间有海盗，因此每一条边都有一个危险指数（权重），然后给出一段必须经过的路线，求从一号小岛走到N号小岛最小的危险指数是多少。

先介绍一下Floyd算法吧：

Floyd（弗洛伊德）算法是用来求解带权图（无论正负）中的多源最短路问题。算法的原理是动态规划。

用dist(i,j,k)表示从顶点i到顶点j只经过前k个顶点的最短路的长度。那么只有如下两种情况

1.i,j之间的最短路不经过k+1，dist(i,j,k+1)<-dist(i,j,k)

2.i,j之间的最短路经过k+1，dist(i,j,k+1)<-dist(i,k+1,k)+dist(k+1,j,k)。

所以dist(i,j,k+1)<-min{dist(i,j,k),dist(i,k+1,k)+dist(k+1,j,k)}。

_在算法实现的时候可以省略掉k那一维，只需要用一个二维数组即可。

——《ACM国际大学生程序设计竞赛 知识与入门》

AC代码见下。

其中dist为dp数组，order用于储存要求必须走的那一段路程。

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

const int maxn = 105;  
    
int n, m, ans = 0;
int dist[maxn][maxn];
int order[10010];
    
int main() {
    cin >> n >> m;
    for(int i = 1; i <= m; i++) cin >> order[i];
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++) {
            cin >> dist[i][j];
        }
        
    for(int k = 1; k <= n; k++)
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                
    for(int i = 2; i <= m; i++) ans += dist[order[i - 1]][order[i]];
    ans += dist[1][order[1]];
    ans += dist[order[m]][n];
        
    cout << ans;
}