【链接】h在这里写链接


【题意】


给你任意两点之间的最短路。
让你求出原图。
或者输出原图不存在。
输出原图的边长总和的最小值。

【题解】


floyd算法。
先在原有的矩阵上。
做一遍floyd.
如果还能扩展。
也即存在w[i][j] > w[i][k]+w[k][j];
则无解。
否则。
先把所有w[i][j]加上(i<j),记为ans;
也即先在任意两点之间都连一条边.边的长度对应了两点之间最短路。
然后考虑什么时候可以减少一条边。
可以在做floyd的时候.
如果出现w[i][j] == w[i][k]+w[k][j];
则可以删掉(i,j)这一条边。
因为这条边是多余的了。
没有必要再建它。
(不要重复删边,用个bo判重一下就好)
则ans-=w[i][j];
最后输出ans即可。


【错的次数】


0

【反思】


在这了写反思

【代码】

#include <bits/stdc++.h>
using namespace std; const int N = 3e2; int n;
long long g[N+10][N+10],ans;
bool bo[N+10][N+10]; int main(){
//freopen("F:\\rush.txt","r",stdin);
ios::sync_with_stdio(0),cin.tie(0);
cin >> n;
for (int i = 1;i <= n;i++)
for (int j = 1;j <= n;j++){
cin >> g[i][j];
if (j > i) ans+=g[i][j];
} for (int i = 1;i <= n;i++)
for (int j = 1;j <= n;j++)
if (g[i][j]!=g[j][i])
return cout <<-1<<endl,0; for (int k = 1;k <= n;k++)
for (int i = 1;i <= n;i++)
if (k!=i)
for (int j = 1;j <= n;j++)
if (k!=j && i!=j)
if (g[i][j]>g[i][k]+g[k][j])
return cout<<-1<<endl,0;
else
if (g[i][j]==g[i][k]+g[k][j] && !bo[i][j]){
ans -= g[i][j];
bo[i][j] = true;
bo[j][i] = true;
}
cout << ans << endl; return 0;
}
05-18 21:46