@[spring_is_coming](/user/791890)
弗洛伊德算法时间复杂度为 $ \Theta(n^3) $
且题目给定 $n \leq 10^3$，因此会超时。
建议更换最短路算法。
by Prms_Prmt @ 2023-08-17 21:51:47
另：[此帖](https://www.luogu.com.cn/discuss/659548)提及题解并非规范：作者通过编译器优化`#pragma`让错误的时间复杂度通过此题。
by Prms_Prmt @ 2023-08-17 21:57:15
```cpp
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")
#include <immintrin.h>
#include <emmintrin.h>
#include <iostream>
#include <cstring>
using namespace std;
#define re register
int arr[1005][1005];
int n,m,a,b,c,ans;
void read(int& a)
{
int s=0,w=1;
char ch=getchar();
while (ch<'0'||ch>'9'){
if (ch=='-')
w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
s=s*10+ch-'0';
ch=getchar();
}
a=s*w;
}
int main(){
read(n);
read(m);
memset(arr,0x3f,sizeof(arr));
for(re int i=1;i<=m;i++){
read(a);read(b);read(c);
arr[a][b]=min(arr[a][b],c);
}
for(re int k=1;k<=n;k++)
for(re int i=1;i<=n;i++)
for(re int j=1;j<=n;j++)
if(arr[i][j]>arr[i][k]+arr[k][j])
arr[i][j]=arr[i][k]+arr[k][j];
for(re int i=2;i<=n;i++)
ans+=arr[1][i]+arr[i][1];
cout << ans;
return 0;
}
```
你指的是这样吗？但是会CE
by springisnotcoming @ 2023-08-17 22:21:08
~~主要是不想写最短路~~
by springisnotcoming @ 2023-08-17 22:21:49
是不是洛谷不支持gcc指令集优化啊，在本地可以正常运行
by springisnotcoming @ 2023-08-17 22:26:56
算了，还是写某D开头的算法吧（）
by springisnotcoming @ 2023-08-17 22:34:19