最短路：请柬
2025-03-16 17:05:10
发布于：北京
25阅读
0回复
0点赞
#include<bits/stdc++.h>
using namespace std;
const long long maxn=1005;
long long e[maxn][maxn],dis[maxn],vis[maxn],ee[maxn][maxn];
void dij(long long n,long long s){
for(long long i=0;i<=n;i++){
dis[i]=1e9;
}
dis[s]=0;
for(long long i=1;i<=n;i++){
long long u=0;
for(long long j=1;j<=n;j++){
if(!vis[j] && dis[j]<dis[u]) u=j;
}
vis[u]=1;
for(long long j=1;j<=n;j++){
if(e[u][j]){
long long v=j;
long long w=e[u][j];
if(dis[v]>dis[u]+w){
dis[v]=dis[u]+w;
}
}
}
}
}
void dji(long long n,long long s){
for(long long i=0;i<=n;i++){
vis[i]=0;
dis[i]=1e9;
}
dis[s]=0;
for(long long i=1;i<=n;i++){
long long u=0;
for(long long j=1;j<=n;j++){
if(!vis[j] && dis[j]<dis[u]) u=j;
}
vis[u]=1;
for(long long j=1;j<=n;j++){
if(ee[u][j]){
long long v=j;
long long w=ee[u][j];
if(dis[v]>dis[u]+w){
dis[v]=dis[u]+w;
}
}
}
}
}
int main(){
long long n,m;
cin>>n>>m;
for(long long i=0;i<m;i++){
long long u,v,w;
cin>>u>>v>>w;
long long tmp=e[u][v]?e[u][v]:1e9;
e[u][v]=min(tmp,w);
swap(u,v);
tmp=ee[u][v]?ee[u][v]:1e9;
ee[u][v]=min(tmp,w);
}
long long ans=0;
dij(n,1);
for(long long i=1;i<=n;i++){
ans+=dis[i];
}
dji(n,1);
for(long long i=1;i<=n;i++){
ans+=dis[i];
}
cout<<ans;
return 0;
}
这里空空如也
有帮助，赞一个