#include<cstdio>//十足的水题
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<string>
#include<iostream>
#include<queue>
#include<iomanip>
#include<algorithm>
using namespace std;
const int N=1000010;

struct edge
{
	int v,nx,w;
}ee[N],e[N];
int n,m,headd[N],head[N],id;
int l,r,q[2*N],d[N];
bool vis[N];

void add(int u,int v,int w)
{
	id++;
	e[id].v=v;e[id].w=w;e[id].nx=head[u];head[u]=id;
	ee[id].v=u;ee[id].w=w;ee[id].nx=headd[v];headd[v]=id;
}

long long spfaa()
{
	int i,j,u,v;
	memset(d,0x7f,sizeof(d));
	memset(vis,false,sizeof(vis));
	l=1;r=1;q[1]=1;d[1]=0;vis[1]=true;
	while(l<=r)
	{
		u=q[l];l++;
		vis[u]=false;
		for(i=head[u];i!=-1;i=e[i].nx)
		{
			v=e[i].v;
			if(d[u]+e[i].w<d[v])
			{
				d[v]=d[u]+e[i].w;
				if(!vis[v])
				{
					r++;q[r]=v;
				}
			}
		}
	}
	long long res=0;
	for(i=2;i<=n;i++) res+=d[i];
	return res;
}

long long spfab()
{
	int i,j,u,v;
	memset(d,0x7f,sizeof(d));
	memset(vis,false,sizeof(vis));
	l=1;r=1;q[1]=1;d[1]=0;vis[1]=true;
	while(l<=r)
	{
		u=q[l];l++;
		vis[u]=false;
		for(i=headd[u];i!=-1;i=ee[i].nx)
		{
			v=ee[i].v;
			if(d[u]+ee[i].w<d[v])
			{
				d[v]=d[u]+ee[i].w;
				if(!vis[v])
				{
					r++;q[r]=v;
				}
			}
		}
	}
	long long res=0;
	for(i=2;i<=n;i++) res+=d[i];
	return res;
}

int main()
{
	int i,j,cas,a,b,c;
	scanf("%d",&cas);
	while(cas--)
	{
		scanf("%d%d",&n,&m);
		id=0;
		memset(head,-1,sizeof(head));
		memset(headd,-1,sizeof(headd));
		for(i=1;i<=m;i++)
		{
			scanf("%d%d%d",&a,&b,&c);
			add(a,b,c);
		}
		printf("%I64d\n",spfaa()+spfab());
	}
	return 0;
}

• Re:第100题纪念，附AC代码 (1854) lxyzsmy 2021-08-09 16:18:56
• Re:第100题纪念，附AC代码 (1854) zhishou0718 2022-07-24 14:44:00