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

绿绵羊 · 2019-03-09 22:29:49 · 题解

这道题要用的是floyd算法，当然，多做几次dijkstra算法用来打表也是可以的。

floyd算法的精髓是：利用枚举一个点，使其优化其他两点距离，从而找到最短路。

floyd是O（n^3）算法，所以用在这道题上的时间复杂度还是很可观的。

#include <bits/stdc++.h>
using namespace std;
long long GA[111][111], r[11111];
int main()
{
    long long n, m, i, j, c, t=0;
    cin >> n >> m;
    for (i=1; i<=m; i++) cin >> r[i];
    for (i=1; i<=n; i++)
        for (j=1; j<=n; j++) cin >> GA[i][j];
    for (c=1; c<=n; c++) //枚举中间优化点 
        for (i=1; i<=n; i++) //枚举起始点 
            for (j=1; j<=n; j++) //枚举终止点 
                if (GA[i][c]+GA[c][j]<GA[i][j]) GA[i][j]=GA[i][c]+GA[c][j]; //如果可以优化，那就更改数值 
    for (i=2; i<=m; i++) t+=GA[r[i-1]][r[i]]; //按照邻接矩阵里的数据输出 
    cout << t << endl;
    return 0;
}

借用一下自己曾说过的话为大家解释一下为什么floyd好：

用floyd的原因是floyd是多源最短路径算法，而且代码量小，代码难度小，思维难度也更小，而dijkstra是单源最短路径算法，套上循环后时间复杂度在这道题上和dijkstra几乎一样，所以被人嫌弃了。

当然，如果这道题把M变成2，那么dijkstra就是更好的选择了。