邮递员送信
Description
有一个邮递员要送东西，邮局在结点1。他总共要送N−1样东西，其目的地分别是2−N。由于这个城市的交通比较繁忙，因此所有的道路都是单行的，共M条道路，通过每条道路需要一定的时间。这个邮递员每次只能带一样东西。求送完这N−1样东西并且最终回到邮局最少需要多少时间。
Input
输入文件第一行包括一个正整数N和M；
接下来M行，每行三个正整数U,V,W，表示该条道路为从U到V的，且通过这条道路需要W的时间。满足1 <= U,V、N <= 1000 , 1≤W≤10000，输入保证任意两点都能互相到达。
Output
输出仅一行，包含一个整数，为最少需要的时间。
Samples
Input Copy
5 10 2 3 5 1 5 5 3 5 6 1 2 8 1 3 8 5 3 4 4 1 8 4 5 3 3 5 6 5 4 2
Output
83
Hint
对于30%的数据，满足1≤N≤200
对于100%的数据，满足1≤N≤1000,1≤M≤100000
本体需要注意的是点之间联通的关系为单向边，就不能用 dis[i] 代表目标点到起点的最短距离，只能表示起点到目标点的最短距离
对于从起点到目标点的情况下来说，我们可以通过按照输入顺序 u v w,建一条从u到v且边权为w的有向边
对于从目标点返回起点的情况来讲，我们可以通过按照与输入顺序 u v w 相反的顺序建立从 v 到 u 且边权为 w 的有向边，建立反图（多起点，单一终点）
这个题可以建立两个独立的图网络，跑两次Dijkstra，为了方便，也可以在建立第二个图网络的时候将所有点的编号加上 n ,得到建立的反图
注意下边权和标记数组的初始化
Main_Code():
int n,m; int head[maxn]; struct node{ int u; int v; int w; int next; }e[maxn]; int cnt = 0; void add(int u,int v,int w){ e[cnt].u = u; e[cnt].v = v; e[cnt].w = w; e[cnt].next = head[u]; head[u] = cnt++; } int dis[maxn]; bool vis[maxn]; void init(){ for(int i=1;i<maxn;i++) { dis[i] = 0x3f3f3f3f; vis[i] = 0; ///head[i] = -1; } } struct edg{ int pnt; int dist; bool operator < (const edg&aaa) const{ return dist > aaa.dist; } }; void dij(int st){ priority_queue<edg> que; dis[st] = 0; que.push((edg){st,0}); while(que.size()){ edg cur = que.top(); que.pop(); int pu = cur.pnt; int d = cur.dist; if(vis[pu]) continue; vis[pu] = 1; for(int i=head[pu];~i;i = e[i].next){ int v = e[i].v; int w = e[i].w; if(vis[v] == 0 && dis[pu] + w < dis[v]){ dis[v] = dis[pu] + w; que.push((edg){v,dis[v]}); } } } } int main() { n=read,m=read; init(); memset(head,-1,sizeof head); for(int i=1;i<=m;i++){ int u=read,v=read,w=read; add(u,v,w); add(n+v,n+u,w); } ll ans = 0; dij(1); for(int i=2;i<=n;i++) ans += dis[i]; init(); dij(n+1); for(int i=1+n;i<=2*n;i++) ans += dis[i]; cout<<ans; return 0; }
