判重边 + `0x3f3f3f3f3f3f3f3f`
by _xm_ @ 2023-11-20 01:13:30
@[_xm_](/user/821481)
是这样吗？
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define P pair<ll,ll>
#define w first
#define s second
const int N=5e5+5;
ll dis[N];
ll g[2001][2001];
ll g2[2001][2001];
bool vis[N];
ll n,m;
inline ll read()
{
ll ans=0,f=1;
char x=getchar();
while(x<'0' || x>'9')
{
if(x=='-') f=-1;
x=getchar();
}
while(x>='0' && x<='9')
{
ans=(ans<<3)+(ans<<1)+x-'0';
x=getchar();
}
return ans*f;
}
void ds(ll x)
{
memset(dis,0x3f3f3f3f3f3f3f3f,sizeof(dis));
memset(vis,0,sizeof(vis));
priority_queue<P,vector<P>,greater<P> > q;
set<ll> s;
dis[x]=0;
q.push({0,x});
while(q.size())
{
P cur=q.top();
q.pop();
if(vis[cur.s]) continue;
vis[cur.s]=1;
for(int i=1;i<=n;i++)
{
if(g[cur.s][i]!=0x3f3f3f3f3f3f3f3f)
{
if(dis[i]>g[cur.s][i]+cur.w)
{
dis[i]=g[cur.s][i]+cur.w;
if(!s.count(i))
{
q.push({dis[i],i});
s.insert(i);
}
}
}
}
}
}
void ds2(ll x)
{
memset(dis,0x3f3f3f3f3f3f3f3f,sizeof(dis));
memset(vis,0,sizeof(vis));
priority_queue<P,vector<P>,greater<P> > q;
dis[x]=0;
set<ll> s;
q.push({0,x});
while(q.size())
{
P cur=q.top();
q.pop();
if(vis[cur.s]) continue;
vis[cur.s]=1;
for(int i=1;i<=n;i++)
{
if(g2[cur.s][i]!=0x3f3f3f3f3f3f3f3f)
{
if(dis[i]>g2[cur.s][i]+cur.w)
{
dis[i]=g2[cur.s][i]+cur.w;
if(!s.count(i))
{
q.push({dis[i],i});
s.insert(i);
}
}
}
}
}
}
int main()
{
memset(g,0x3f3f3f3f3f3f3f3f,sizeof(g));
memset(g2,0x3f3f3f3f3f3f3f3f,sizeof(g2));
n=read();
m=read();
for(int i=1;i<=m;i++)
{
ll u,v,w;
u=read();
v=read();
w=read();
g[u][v]=w;
g2[v][u]=w;
}
ll ans=0;
ds(1);
for(int i=2;i<=n;i++) ans+=dis[i];
ds2(1);
for(int i=2;i<=n;i++) ans+=dis[i];
printf("%d\n",ans);
return 0;
}
```
by Tanlun_np @ 2023-11-20 18:59:01
@[_xm_](/user/821481)
谢谢大佬，已AC
by Tanlun_np @ 2023-11-20 20:07:23