对于

idgg007 @ 2020-05-02 09:25:10

#include<iostream>
#include<cstring>
using namespace std;
int zhen[1005][1005];//邻接矩阵 
int main(){
    long long ans=0;
    int n,m;
    cin>>n>>m;
    memset(zhen,0x3f,sizeof(zhen));
    for(int i=0,a,b,w;i<m;i++){
        cin>>a>>b>>w;
        zhen[a][b]=w;
    }for(int k=1;k<=n;k++)
        for(int j=1;j<=n;j++)
            for(int i=1;i<=n;i++)
                if(k!=i&&j!=i&&k!=j&&zhen[j][i]>zhen[k][i]+zhen[j][k]){
                    zhen[j][i]=zhen[k][i]+zhen[j][k];
                }
    for(int i=2;i<=n;i++){
        ans+=zhen[1][i];
        ans+=zhen[i][1];
    }cout<<ans;
    return 0;
}

by zhy137036 @ 2020-05-02 09:40:17

@idgg007 等您过了踹我一脚。

我想看奇迹。

by zhy137036 @ 2020-05-02 09:40:48

建议重学学习复杂度（包括时间和空间）

by Vocalise @ 2020-05-02 09:44:55

如果仅仅是因为不想重新写代码才发这个帖子的话，请去下一题吧

by LeavingZzz @ 2020-05-02 09:46:31

lz怕是觉得万物皆可floyd（

by EliClark266 @ 2020-05-02 10:00:19

@idgg007 讲真看到三重循环我服了

简单解释一下：

a = 1;

这是O(1)

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

这是O(n)

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

这是O(n^2) 所以您看看您的复杂度吧……

并且我看你[1005][1005]的做法加上O(n^3)的复杂度，能过我ak ioi

by EliClark266 @ 2020-05-02 10:01:02

我指的是您用这个做法

by Rainy7 @ 2020-05-02 10:11:53

这个做法空间时间都不可能emm

by __gcd @ 2020-05-02 10:13:39

@idgg007 弱弱问一句Jasontra是什么……

by lowAltitudeFlyer @ 2020-05-02 16:58:35

@idgg007 等您过了踹我一脚。

我想看奇迹。

by PersistentLife @ 2020-05-02 16:58:46

@idgg007 邻接表了解一下