$$\color{Purple}{kuangbin题解目录}$$
描述
给定一个 $n$ 个点 $m$ 条边的无重边无自环的有向图。
点的编号 $1 \\sim n$。
任意两点之间均可相互抵达。
请你计算,从点 $1$ 到其他所有点的最短路径长度以及从其他所有点到点 $1$ 的最短路径长度,并将这 $2 \\times (n-1)$ 个最短路径长度相加后输出结果。
输入格式
第一行包含整数 $T$,表示共有 $T$ 组测试数据。
每组数据第一行包含两个整数 $n,m$。
接下来 $m$ 行,每行包含三个正整数 $a,b,c$,表示从点 $a$ 到点 $b$ 存在一条边,长度为 $c$。
输出格式
每组数据输出一行,一个整数表示结果。
数据范围
$1 \\le T \\le 10$,
$1 \\le n,m \\le 10^6$,
$1 \\le a,b \\le n$,
一组数据中所有的 $c$ 相加之和不超过 $10^9$。
输入样例:
2
2 2
1 2 13
2 1 33
4 6
1 2 10
2 1 60
1 3 20
3 4 10
2 4 5
4 1 50
输出样例:
46
210
思路
代码
// Problem: 最短路径和
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/4249/
// Memory Limit: 64 MB
// Time Limit: 3000 ms
// Date: 2023-01-26 15:47:39
//
// Powered by CP Editor (https://cpeditor.org)
/**
* @author : SDTBU_LY
* @version : V1.0.0
* @上联 : ac自动机fail树上dfs序建可持久化线段树
* @下联 : 后缀自动机的next指针DAG图上求SG函数
**/
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#define MAXN 1000010
#define MAXM 2000010
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
int t,n,m;
int head[2][MAXN],ed[MAXM],nex[MAXM],val[MAXM],idx;
int dist[2][MAXN];
int vis[MAXN];
void add(int op,int a,int b,int c)
{
ed[idx]=b;
val[idx]=c;
nex[idx]=head[op][a];
head[op][a]=idx++;
}
void dijkstra(int start,int op)
{
memset(dist[op],0x3f,sizeof(dist[op]));
memset(vis,0,sizeof(vis));
priority_queue<PII,vector<PII>,greater<PII> > q;
q.push({0,start});
dist[op][start]=0;
while(q.size()>0)
{
PII temp=q.top();
q.pop();
int temp_dis=temp.first,temp_pos=temp.second;
if(vis[temp_pos]==1)
continue;
vis[temp_pos]=1;
for(int i=head[op][temp_pos];i!=-1;i=nex[i])
{
int j=ed[i];
if(vis[j]==1)
continue;
if(dist[op][j]>temp_dis+val[i])
{
dist[op][j]=temp_dis+val[i];
q.push({dist[op][j],j});
}
}
}
}
int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0),cout.tie(0);
cin >> t;
while(t--)
{
cin >> n >> m;
memset(head,-1,sizeof(head));
idx=0;
for(int i=1;i<=m;i++)
{
int a,b,c;
cin >> a >> b >> c;
add(0,a,b,c);//正向建边(求1到每个点的距离)
add(1,b,a,c);//反向建边(求每个点到1的距离)
}
dijkstra(1,0);
dijkstra(1,1);
ll res=0;//结果记得开long long
for(int i=2;i<=n;i++)
res+=dist[0][i]+dist[1][i];
cout << res << endl;
}
return 0;
}
```