提交记录

代码（Dijkstra+堆优化）：

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int maxn = 1000*2 + 10;
const int maxm = 100000 + 10;
struct Edge{
	int u,v,w;
	int next;
}e[maxm];
int en=0;
bool vis[maxn];
int h[maxn];
int dis[maxn],n,m,sum;
priority_queue<PII,vector<PII>,greater<PII> > q;

void addEdge(int x,int y,int z){
	en++;
	e[en].u=x;
	e[en].v=y;
	e[en].w=z;
	e[en].next=h[x];
	h[x]=en;
}

void Dijkstra(int s){
	for(int i=1;i<=n*2;i++){
		vis[i]=0;
		dis[i]=1e18 / 3;
	}
	dis[s]=0;
	q.push(make_pair(0,s));
	while(!q.empty()) {
		int k=q.top().second;
		q.pop();
		if(!vis[k]) {
			vis[k]=true;
			for(int j=h[k];j>0;j=e[j].next){
				int v=e[j].v;
				int w=e[j].w;
				if(dis[v]>dis[k]+w){
					dis[v]=dis[k]+w;
					q.push(make_pair(dis[v],v));
				}
			}
		}
	}
}

signed main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		addEdge(u,v,w);
		addEdge(v+n,u+n,w);
	}
	Dijkstra(1);
	for(int i=2;i<=n;i++){
		sum+=dis[i];
	}
	Dijkstra(1+n);
	for(int i=2+n;i<=n*2;i++){
		sum+=dis[i];
	}
	cout<<sum<<endl;
	return 0;
}