C++(clang++11) 解法, 执行用时: 508ms, 内存消耗: 48468K, 提交时间: 2020-12-19 17:11:18

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m,dis[2000020],head[2000020],cnt,ans;
bool v[2000020];
struct edge{
	ll to,next,z;
}a[2000020];
void add(int x,int y,int z){
	a[++cnt].to=y;
	a[cnt].z=z;
	a[cnt].next=head[x];
	head[x]=cnt;
}
void dij(int x){
	
	priority_queue<pair<int,int> > q;
	q.push(make_pair(0,x));
	dis[x]=0;
	while(q.size()){
		int now=q.top().second;
		q.pop();
		if(v[now]) continue;
		v[now]=1;
		for(int i=head[now];i;i=a[i].next){
			int y=a[i].to;
			if(dis[y]>dis[now]+a[i].z){
				dis[y]=dis[now]+a[i].z;
				q.push(make_pair(-dis[y],y));
			}
		} 	
	}
}
int main(){
	scanf("%lld %lld",&n,&m);
	for(int i=1;i<=m;i++){
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		add(x,y,z);add(y+n+2,x+n+2,z);
	}
	for(int i=1;i<=n*2+100;i++)
	dis[i]=0x7fffffff;
	dij(1);dij(n+2+1);
	for(int i=2;i<=n;i++)
	ans+=dis[i]+dis[n+2+i];
	cout<<ans;
}