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;
}| 弗洛伊德算法 | MLE |
|---|
有没有压空间的方法
by XeCtera @ 2020-05-02 09:26:41
立方过百万？
by idgg007 @ 2020-05-02 09:26:56
求助帖
by impuk @ 2020-05-02 09:27:04
@idgg007
by idgg007 @ 2020-05-02 09:27:49
@一只爬行者 大佬请问有什么高明的见解
by XeCtera @ 2020-05-02 09:28:43
@idgg007 请使用dijkstra堆优化
by impuk @ 2020-05-02 09:28:53
@idgg007 我有且只有一个见解。
我遇到了百年一遇的卡常带师
别人
by idgg007 @ 2020-05-02 09:29:17
全MLE有压空间的方法吗我以前把时间放在首位
by XeCtera @ 2020-05-02 09:29:31
没有
by idgg007 @ 2020-05-02 09:30:11
懒癌晚期患者，打了代码不想再重新做了
by impuk @ 2020-05-02 09:30:15
草，我是傻逼，弗洛伊德确实没有压空间的方法（？）