Floyd（三倍经验）

前言

如果你是来看三倍经验的请翻到最底下

题意

简单来说就是在一个有向图中求$\sum_{i=2}^n e[1][i]+e[i][1]$，其中e[i][j]代表从点i到点j的最短距离

解析

这道题的正解是先跑一遍单源最短路再反向建边再单源最短路然后就成了但是用堆优化的dijkstra的代码太长了（其实也没多长）所以本蒟蒻决定用普通dijkstra反正$n^2$也能过但是还是觉得太长了想试试$n^3$的Floyd碰碰运气，于是：

标程

#include <iostream>
using namespace std;
const int INF = 1e9;
int e[1005][1005];
int main(){
    int n, m, x, y, z;
    cin >> n >> m;
    for (int i = 1;i <= n;i++){
        for (int j = 1;j <= n;j++){
            if (i == j){
                e[i][j] = 0;
            }else{
                e[i][j] = INF;
            }
        }
    }
    for (int i = 1;i <= m;i++){
        cin >> x >> y >> z;
        e[x][y] = min(e[x][y], z); // 小心重边
    }
    for (int k = 1;k <= n;k++){
        for (int i = 1;i <= n;i++){
            for (int j = 1;j <= n;j++){
                if (e[i][j] > e[i][k] + e[k][j]){
                    e[i][j] = e[i][k] + e[k][j];
                }
            }
        }
    }
    long long sum = 0;
    for (int i = 2;i <= n;i++){
        sum += e[1][i] + e[i][1];
    }
    cout << sum;
}

代码没啥技术含量注释就不写了。

后记

ACGO的数据好水啊我500+ms过了，上洛谷还得开快读才能过
然后三倍经验：Cow Party S Cow Party S （虽然题面一样但两个题目不一样）
ps:如果你用的是dijkstra那么还有：ACGOA22641

上面这两道题还有这题洛谷上都有