题目
有一个邮递员要送东西，邮局在节点 1。他总共要送 n−1 样东西，其目的地分别是节点 2 到节点 n。由于这个城市的交通比较繁忙，因此所有的道路都是单行的，共有 m 条道路。这个邮递员每次只能带一样东西，并且运送每件物品过后必须返回邮局。求送完这 n−1 样东西并且最终回到邮局最少需要的时间。
输入格式
第一行包括两个整数，n 和 m，表示城市的节点数量和道路数量。
第二行到第 (m+1) 行，每行三个整数 ,u,v,w , 表示从 u 到 v 有一条通过时间为 w 的道路。
输出格式
输出仅一行，包含一个整数，为最少需要的时间。
数据范围
1 ≤ n ≤ 1e3 , 1 ≤ m ≤ 1e5
1 ≤ u,v ≤ n , 1 ≤ w ≤ 1e4
输入保证任意两点都能互相到达。
思路概述
经典的 SPFA 变式。
如果邮递员每次都能够“瞬移”回邮局，那就是简单的单源最短路径。普通的SPFA 秒过。
但邮递员要返回邮局。
暴力思路是用 Dijkstra 扫一遍。但是时间复杂度会爆。
考虑以下思路：因为边的边权恒不变，所以多开一倍空间，把边“倒过来”，这样能变成又一个单源最短路径。只需要再SPFA一遍就行。
注意： 空间最好开两倍，不然容易弄混
代码
#include <bits/stdc++.h>
#define N 1010
#define M 100010
using namespace std;
int n,m,u,v,w,x,ans;
int ver[2*M],edge[2*M],nxt[2*M],tot;
int head[2*N];int d[2*N]; bool vis[2*N];
queue<int> que;int main() {scanf("%d%d",&n,&m);for(int i=1;i<=m;i++) {scanf("%d%d%d",&u,&v,&w);tot++;ver[tot]=v; edge[tot]=w;nxt[tot]=head[u]; head[u]=tot;ver[tot+m]=u+n; edge[tot+m]=w;nxt[tot+m]=head[v+n]; head[v+n]=tot+m;}memset(d,0x3f,sizeof(d));d[1]=0; vis[1]=true;que.push(1);while(!que.empty()) {x=que.front();que.pop(); vis[x]=false;for(int i=head[x];i;i=nxt[i])if(d[ver[i]]>d[x]+edge[i]) {d[ver[i]]=d[x]+edge[i];que.push(ver[i]); vis[ver[i]]=true;}}for(int i=2;i<=n;i++) ans+=d[i];memset(d,0x3f,sizeof(d));memset(vis,false,sizeof(vis));d[n+1]=0; vis[n+1]=true;que.push(n+1);while(!que.empty()) {x=que.front();que.pop(); vis[x]=false;for(int i=head[x];i;i=nxt[i])if(d[ver[i]]>d[x]+edge[i]) {d[ver[i]]=d[x]+edge[i];que.push(ver[i]); vis[ver[i]]=true;}}for(int i=2+n;i<=n+n;i++) ans+=d[i];printf("%d\n",ans);return 0;
}