题解 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 = ;  

 int n, m, ans = ;

 int dist[maxn][maxn];

 int order[];

 int main() {

     cin >> n >> m;

     for(int i = ; i <= m; i++) cin >> order[i];

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

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

             cin >> dist[i][j];

         }

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

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

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

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

     for(int i = ; i <= m; i++) ans += dist[order[i - ]][order[i]];

     ans += dist[][order[]];

     ans += dist[order[m]][n];

     cout << ans;

 }

巴特西

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

最新文章

热门文章