T6
2024-08-15 14:46:47
发布于：浙江
11阅读
0回复
0点赞
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
typedef long long ll;
const ll maxn=1e4+5;
struct node{
ll v,w;
friend bool operator<(node a,node b){
return a.w>b.w;
}
};
int vis[maxn];
ll n,m;
ll u,v,w;
vector<node> G[2][maxn];
ll dis[maxn];
node head;
int pos,next_pos;
ll val;
priority_queue<node> q;
void dij(int x){//x代表当前遍历的是正向地图还是反向地图
memset(dis,INF,sizeof(dis));
memset(vis,0,sizeof(vis));
dis[1]=0;
for (int i=1;i<n;i++){
pos=-1;
for (int j=1;j<=n;j++){
if ((pos==-1 || dis[j]<dis[pos]) && !vis[j]) pos = j;
}
if (pos==-1) break;
vis[pos]=1;
for (int j=0;j<G[x][pos].size();j++){
next_pos=G[x][pos][j].v;
val=G[x][pos][j].w;
if (dis[next_pos]>dis[pos]+val){
dis[next_pos]=dis[pos]+val;
}
}
}
}
ll sum;
int main(){
freopen("travel.in","r",stdin);
freopen("travel.out","w",stdout);
cin>>n>>m;
for (int i=1;i<=m;i++){
cin>>u>>v>>w;
G[0][u].push_back({v,w});//正向存储地图
G[1][v].push_back({u,w});//反向存储地图
}
dij(0);
for (int i=1;i<=n;i++){
sum+=dis[i];
}dij(1);
for (int i=1;i<=n;i++){
sum+=dis[i];
}
cout<<sum;
fclose(stdin);
fclose(stdout);
return 0;
}
这里空空如也
有帮助，赞一个