这道题很适合作为P1629的加强版

因为这道题其实体现了反向建图的高效性

反向建图后：

单终点最短路径→单源最短路径。

因此两边Dij，然后再累计和即可

代码部分不难弄。直接上

先说明以下程序，有1的变量名与第一次dij有关（学生出来）

带2的与第二次dij有关（学生回家）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include<iostream>
#include<cmath>
#include<cstdio>
#include<queue>
#include<cstring>

using namespace std;

int n,m;
int h1[2100000],h2[2100000];
int s1,s2;
struct edge{
	int next,to,dis;
};
int v1[2100000],v2[2100000];  //注意数据范围
long long d1[2100000],d2[2100000];
edge e1[2100000],e2[2100000];

void addedge1(int next,int to,long long dis)
{
	e1[++s1].dis=dis;
	e1[s1].next=h1[next];
	e1[s1].to=to;
	h1[next]=s1;
}

void addedge2(int next,int to,long long dis)
{
	e2[++s2].dis=dis;
	e2[s2].to=to;
	e2[s2].next=h2[next];
	h2[next]=s2;
}

void dij1(int start)
{
	priority_queue <pair<long long,int> > q;  
    //这是优先队列的一个比较容易理解的写法，之所以long long 是因为可总和可能爆int
	memset(d1,0x3f,sizeof(d1));
	memset(v1,0,sizeof(v1));
	q.push(make_pair(0,start));
	d1[1]=0;
	while(!q.empty())
	{
		int i,j;
		long long k;
		int t=q.top().second;
		q.pop();
		if(v1[t]) continue;
		v1[t]=1;
		for(i=h1[t];i;i=e1[i].next)
		{
			j=e1[i].to;
			k=e1[i].dis;
			if(d1[t]+k<d1[j])
			{
				d1[j]=d1[t]+k;
				q.push(make_pair(-d1[j],j));
			}
		}
	}
}

void dij2(int start)
{	
	priority_queue <pair<long long ,int> > q; 
	memset(d2,0x3f,sizeof(d2));
	memset(v2,0,sizeof(v2));
	q.push(make_pair(0,start));
	d2[1]=0;
	while(!q.empty())
	{
		int i,j;
		long long k;
		int t=q.top().second;
		q.pop();
		if(v2[t]) continue;
		
		v2[t]=1;
		for(i=h2[t];i;i=e2[i].next)
		{
			j=e2[i].to;
			k=e2[i].dis;
			if(d2[t]+k<d2[j])
			{
				d2[j]=d2[t]+k;
				q.push(make_pair(-d2[j],j));
			}
		}
	}
}

int main()
{
	int i,j;
	scanf("%d %d",&n,&m);
	for(i=1;i<=m;i++)
	{
		int t1,t2;
		long long t3;
		scanf("%d %d %lld",&t1,&t2,&t3);
		addedge1(t1,t2,t3);
		addedge2(t2,t1,t3);  //反向建图，防止建在同一张图里面影响程序运行
	}
	long long tot=0;
	dij1(1);
	dij2(1);
	for(i=1;i<=n;i++)
	{
		tot+=d1[i]+d2[i];  
	}
	printf("%lld",tot);
	return 0;
}