题目意思：
在有向图中，求1到所有点的最短路之和 + 所有点到1的最短路之和。
本题要点：
1、先求1点 到其他点的单源最短路径 d[i](1 <= i <= n)， 用 dijkstra 算法 和 堆实现。 求出距离的总和 sum。
2、每条路径的方向取反，再求一次 点 1 的单源路径 d1[i](1 <= i <= n)， 求出距离的总和 sum1.
答案就是 sum + sum1;
这里为了避免传参，直接写了两遍 dijkstra 算法。
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int MaxN = 1000010;
int n, m, T, tot, tot1;
int head[MaxN], ver[MaxN], edge[MaxN], Next[MaxN], d[MaxN];
bool vis[MaxN];
int head1[MaxN], ver1[MaxN], edge1[MaxN], Next1[MaxN], d1[MaxN];
bool vis1[MaxN];void add(int x, int y, int z)
{
ver[++tot] = y, edge[tot] = z, Next[tot] = head[x]; head[x] = tot;
}void add1(int x, int y, int z)
{
ver1[++tot1] = y, edge1[tot1] = z, Next1[tot1] = head1[x]; head1[x] = tot1;
}long long dijkstra()
{
memset(d, 0x3f, sizeof d);memset(vis, false, sizeof vis);d[1] = 0;priority_queue<pair<int, int> > q;q.push(make_pair(0, 1));while(q.size()){
int x = q.top().second; q.pop();if(vis[x]) continue;vis[x] = true;for(int i = head[x]; i; i = Next[i]){
int y = ver[i], z = edge[i];if(d[y] > d[x] + z){
d[y] = d[x] + z;q.push(make_pair(-d[y], y));}}}long long ans = 0;for(int i = 1; i <= n; ++i){
ans += d[i];}return ans;
}long long dijkstra1()
{
memset(d1, 0x3f, sizeof d1);memset(vis1, false, sizeof vis1);d1[1] = 0;priority_queue<pair<int, int> > q;q.push(make_pair(0, 1));while(q.size()){
int x = q.top().second; q.pop();if(vis1[x]) continue;vis1[x] = true;for(int i = head1[x]; i; i = Next1[i]){
int y = ver1[i], z = edge1[i];if(d1[y] > d1[x] + z){
d1[y] = d1[x] + z;q.push(make_pair(-d1[y], y));}}}long long ans = 0;for(int i = 1; i <= n; ++i){
ans += d1[i];}return ans;
}int main()
{
scanf("%d", &T);while(T--){
tot = tot1 = 0;memset(head, 0, sizeof head);memset(head1, 0, sizeof head1);memset(Next, 0, sizeof Next);memset(Next1, 0, sizeof Next1);scanf("%d%d", &n, &m);for(int i = 1; i <= m; ++i){
int x, y, z;scanf("%d%d%d", &x, &y, &z);add(x, y, z);add1(y, x, z);}printf("%lld\n", dijkstra() + dijkstra1());}return 0;
}/* 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 */