邮递员送信 单源最短路+反向建边

有一个邮递员要送东西，邮局在节点$1$。他总共要送$n-1$样东西，其目的地分别是节点$2$到节点$n$。所有的道路都是单行的，共有$m$条道路。邮递员每次只能带一样东西，运送每件物品过后必须返回邮局。求送完东西后回到邮局最少需要的时间。
首先送信时，从$1$到$2-n$就是标准的单源最短路；而返回的时候就是多到一，多源最短路比较麻烦。这时候我们邻接矩阵倒过来，从多到一的最短路变式的路径“反向建边”，就变成一到多的单源最短路。

#include<bits/stdc++.h>
using namespace std;
struct node
{int u,v,w,next;
}a[100010],b[100010];
struct New
{int w,now;bool operator <(const New &x)const{return w>x.w;}
};
priority_queue <New> q;
int head[10010],bhead[10010],dis[10010],flag[10010];
int n,m,s,num1,num2,ans=0,x,y;
void add(int u,int v,int w)
{a[++num1].v=v;a[num1].w=w;a[num1].next=head[u];head[u]=num1;b[++num2].v=u;b[num2].w=w;b[num2].next=bhead[v];bhead[v]=num2;
}
void Dij()
{for(int i=1;i<=n;i++)dis[i]=9999999;dis[1]=0;memset(flag,0,sizeof(flag));q.push((New){0,1});while(!q.empty()){New X=q.top();q.pop();int U=X.now;if(flag[U]==1)continue;flag[U]=1;for(int i=head[U];i;i=a[i].next){int V=a[i].v;if(dis[V]>dis[U]+a[i].w){dis[V]=dis[U]+a[i].w;q.push((New){dis[V],V});}}}
}
void Dij2()
{for(int i=1;i<=n;i++)dis[i]=9999999;memset(flag,0,sizeof(flag));dis[1]=0;q.push((New){0,1});while(!q.empty()){New X=q.top();q.pop();int U=X.now;if(flag[U]==1)continue;flag[U]=1;for(int i=bhead[U];i;i=b[i].next){int V=b[i].v;if(dis[V]>dis[U]+b[i].w){dis[V]=dis[U]+b[i].w;q.push((New){dis[V],V});}}}
}
int main()
{cin>>n>>m;for(int i=1;i<=m;i++){cin>>x>>y>>s;add(x,y,s);}Dij();for(int i=2;i<=n;i++)ans+=dis[i];Dij2();for(int i=2;i<=n;i++)ans+=dis[i];cout<<ans<<endl;return 0;
}