霉利的题解（2）

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+10;
ll n,m,x,y,l,dis[N],dis1[N],f[N],f1[N],pre[N],pre1[N],cnt,cnt1,q[5*N],q1[5*N],sum=0;//因为要有正反两图，所以我们要定义双份；
struct edge{
	ll f,t,l,n;
}a[5*N],b[5*N];
void add(ll x,ll y,ll l){
	a[++cnt].f=x;
	a[cnt].t=y;
	a[cnt].l=l;
	a[cnt].n=pre[x];
	pre[x]=cnt;
}//链式前向星(正图)
void add1(ll y,ll x,ll l){
	b[++cnt1].f=y;
	b[cnt1].t=x;
	b[cnt1].l=l;
	b[cnt1].n=pre1[y];
	pre1[y]=cnt1;
}//链式前向星（反图）
//正图spfa模版
void spfa(){
	ll head=1,tail=1;
	q[1]=1;
	f[1]=1;
	dis[1]=0;
	while(head<=tail){
		ll from=q[head];
		for(int i=pre[from];i;i=a[i].n){
			ll to=a[i].t;
			ll len=a[i].l;
			if(dis[from]+len<dis[to]){
				dis[to]=dis[from]+len;
				if(f[to]==0){
					f[to]=1;
					q[++tail]=to;
				}
			}
		}
		f[from]=0;
		head++;
	}
}
//反图spfa
void spfa1(){
	ll head=1,tail=1;
	q1[1]=1;
	f1[1]=1;
	dis1[1]=0;
	while(head<=tail){
		ll from=q1[head];
		for(int i=pre1[from];i;i=b[i].n){
			ll to=b[i].t;
			ll len=b[i].l;
			if(dis1[from]+len<dis1[to]){
				dis1[to]=dis1[from]+len;
				if(f1[to]==0){
					f1[to]=1;
					q1[++tail]=to;
				}
			}
		}
		f1[from]=0;
		head++;
	}
}
int main(){
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%lld%lld%lld",&x,&y,&l);
		add(x,y,l);//正着存入
		add1(y,x,l);//反着存入
	}
	for(int i=1;i<=n;i++){
		dis[i]=2e9+10;
		dis1[i]=2e9+10;
	}//初始化
	spfa();
	spfa1();
	for(int i=2;i<=n;i++){
		sum+=dis[i]+dis1[i];//将所有的点费用加起来
	}
	printf("%lld",sum);
}