题目描述
有一个邮递员要送东西，邮局在节点 \(1\)。他总共要送 \(n-1\) 样东西，其目的地分别是节点 \(2\) 到节点 \(n\)。由于这个城市的交通比较繁忙，因此所有的道路都是单行的，共有 \(m\) 条道路。这个邮递员每次只能带一样东西，并且运送每件物品过后必须返回邮局。求送完这 \(n-1\) 样东西并且最终回到邮局最少需要的时间。
输入格式
第一行包括两个整数， \(n\) 和 \(m\)，表示城市的节点数量和道路数量。
第二行到第 \(m+1\) 行，每行三个整数， \(u, v, w\)，表示从 \(u\) 到 \(v\) 有一条通过时间为 \(w\) 的单行道路。
输出格式
输出仅一行，包含一个整数，为最少需要的时间。
样例数据
输入 #1
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
输出 #1
83
数据范围
- 对于 \(30\%\) 的数据，\(1 \leq n \leq 200\)。
- 对于 \(100\%\) 的数据，\(1 \leq n \leq 10^3\)，\(1 \leq m \leq 10^5\)，\(1\leq u,v \leq n\)，\(1 \leq w \leq 10^4\)。输入保证任意两点都能互相到达。
思路
- 去程：从
1到各个点的最短路径（单源最短路）。
回程：从各个点回到1的最短路径（多源汇点最短路）。
2 . \(dist1[i] =min(dist1[j]+w[j][i])\) , \(dist1[i]\): 从 \(1\) 到 \(i\) 的最短路径
\(dist2[i]=min(w[i][j]+ dist2[j])\), \(dist2[i]\): 从 \(i\) 到 \(1\) 的最短路径 - \(Ans=\sum_{i=1}^{i<=n}(dist1[i]+dist2[i])\)
#include <bits/stdc++.h>
using namespace std;
const int INF=1e9;
int n,m,w[1002][1002],dist1[1002],dist2[1002];
bool Flg[1001];int main() {scanf("%d%d", &n,&m);memset(w,0x3f,sizeof(w));for (int i=1;i<=m;i++) {int x,y,z; cin>>x>>y>>z;w[x][y]=min(w[x][y],z);}for (int i=1;i<=n;i++) dist1[i]=INF;dist1[1]=0;for (int k=1;k<n;k++) {int Min=INF,id=0;for (int i=1;i<=n;i++)if (!Flg[i] && dist1[i]<Min) id=i,Min=dist1[i];Flg[id]=1;for (int i=1;i<=n;i++)if (!Flg[i] && dist1[i]>dist1[id]+w[id][i])dist1[i]=dist1[id]+w[id][i];}memset(Flg,0,sizeof(Flg));for (int i=1;i<=n;i++) dist2[i]=INF;dist2[1]=0;for (int k=1;k<n;k++) {int Min=INF,id=0;for (int i=1;i<=n;i++)if (!Flg[i] && dist2[i]<Min) id=i,Min=dist2[i];Flg[id]=1;for (int i=1;i<=n;i++)if (!Flg[i] && dist2[i]>w[i][id]+dist2[id])dist2[i]=dist2[id]+w[i][id];}long long Ans=0;for (int i=1;i<=n;i++) Ans+=dist1[i]+dist2[i];cout<<Ans<<endl;return 0;
}