xiaoshi_dada @ 2022-10-27 14:50:49
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
const int MAXN=10000006;
struct edge{
int to;
int dis;
int next;
}e[MAXN],e_[MAXN];
int cnt,cnt_,head[MAXN],dis[MAXN],head_[MAXN];
bool vis[MAXN];
void addedge(int u,int v,int d)
{
cnt++;
e[cnt].dis=d;
e[cnt].to=v;
e[cnt].next=head[u];
head[u]=cnt;
}
void addedge_(int u,int v,int d)
{
cnt_++;
e_[cnt_].dis=d;
e_[cnt_].to=v;
e_[cnt_].next=head_[u];
head_[u]=cnt;
}
struct node{
int dis;
int pos;
bool operator <(const node &x)const
{
x.dis<dis;
}
};
priority_queue<node> q;
void dijsktra()
{
dis[1]=0;
q.push({0,1});
while(!q.empty())
{
node tmp=q.top();
q.pop();
int x=tmp.pos,d=tmp.dis;
if(vis[x]) continue;
vis[x]=1;
for(int i=head[x];i;i=e[i].next)
{
int y=e[i].to;
if(dis[y]>dis[x]+e[i].dis)
{
dis[y]=dis[x]+e[i].dis;
if(!vis[y])
{
q.push({dis[y],y});
}
}
}
}
}
void dijsktra_()
{
dis[1]=0;
q.push({0,1});
while(!q.empty())
{
node tmp=q.top();
q.pop();
int x=tmp.pos,d=tmp.dis;
if(vis[x]) continue;
vis[x]=1;
for(int i=head_[x];i;i=e_[i].next)
{
int y=e_[i].to;
if(dis[y]>dis[x]+e_[i].dis)
{
dis[y]=dis[x]+e_[i].dis;
if(!vis[y])
{
q.push({dis[y],y});
}
}
}
}
}
signed main()
{
int ans=0;
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int u,v,d;
cin>>u>>v>>d;
addedge(u,v,d);
addedge_(v,u,d);
}
for(int i=1;i<=n;i++)
{
dis[i]=0x7fffffff;
}
dijsktra();
for(int i=1;i<=n;i++)
{
// cout<<dis[i]<<" ";
ans+=dis[i];
}
// cout<<endl;
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++)
{
dis[i]=0x7fffffff;
}
dijsktra_();
for(int i=1;i<=n;i++)
{
// cout<<dis[i]<<" ";
ans+=dis[i];
}
// cout<<endl;
cout<<ans<<endl;
return 0;
}
by ccxswl @ 2023-01-11 18:26:08
@xiaoshi_dada 您的重载运算符没有返回值
……
struct node{
int dis;
int pos;
bool operator <(const node &x)const
{
return x.dis<dis;
// ^要有return
}
};
……