```cpp
#include <iostream>
#include <cstring>
#include <queue>
#define pii pair<int,int>
#define mp(a,b) make_pair((a),(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;
const int maxn=1e3+1,maxm=1e5+1,inf=1e4+1;
struct node{
int to,nxt,w;
node():w(inf){}
};
node e1[maxm],e2[maxm];
priority_queue<pii,vector<pii>,greater<pii> >H;
int n,m,u,v,w,tot,ans,dis[maxn],adis[maxn],head1[maxn],head2[maxn];
bool vis[maxn];
inline void link(int x,int y,int z,int f){
if(f){
e1[++tot].to=y;
e1[tot].w=Min(z,e1[tot].w);
e1[tot].nxt=head1[x];
head1[x]=tot;
}
else{
e2[++tot].to=y;
e2[tot].w=Min(z,e2[tot].w);
e2[tot].nxt=head2[x];
head2[x]=tot;
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) dis[i]=adis[i]=inf;
for(int i=1;i<=m;i++) scanf("%d%d%d",&u,&v,&w),link(u,v,w,1),link(v,u,w,0);
dis[1]=adis[1]=0,H.push(mp(0,1));
while(!H.empty()){
int dist=H.top().first,id=H.top().second;
H.pop();
if(vis[id]) continue;
vis[id]=true;
for(int i=head1[id];i;i=e1[i].nxt)
if(dis[id]+e1[i].w<dis[e1[i].to])
dis[e1[i].to]=dis[id]+e1[i].w,H.push(mp(dis[e1[i].to],e1[i].to));
}
H.push(mp(0,1)),memset(vis,false,sizeof(vis));
while(!H.empty()){
int dist=H.top().first,id=H.top().second;
H.pop();
if(vis[id]) continue;
vis[id]=true;
for(int i=head2[id];i;i=e2[i].nxt)
if(adis[id]+e2[i].w<adis[e2[i].to])
adis[e2[i].to]=adis[id]+e2[i].w,H.push(mp(adis[e2[i].to],e2[i].to));
}
for(int i=2;i<=n;i++) ans+=dis[i]+adis[i];
printf("%d",ans);
return 0;
}
```
by yszkddzyh @ 2023-01-23 10:44:34
已A，本帖结
by yszkddzyh @ 2023-01-23 10:52:50