$$邮递员送信$$

题目链接：$luogu1629$

题目

有一个邮递员要送东西，邮局在节点 $1$。他总共要送 $n-1$ 样东西，其目的地分别是节点 $2$ 到节点 $n$。由于这个城市的交通比较繁忙，因此所有的道路都是单行的，共有 $m$ 条道路。这个邮递员每次只能带一样东西，并且运送每件物品过后必须返回邮局。求送完这 $n-1$ 样东西并且最终回到邮局最少需要的时间。

输入

第一行包括两个整数，$n$ 和 $m$，表示城市的节点数量和道路数量。

第二行到第 $(m+1)$ 行，每行三个整数，$u,v,w$，表示从 $u$ 到 $v$ 有一条通过时间为 $w$ 的道路。

输出

输出仅一行，包含一个整数，为最少需要的时间。

样例输入

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

样例输出

83

数据范围

对于 $30\%$ 的数据，$1\le n\le 200$。

对于 $100\%$ 的数据，$1\le n\le 10^3$ ，$1\le m\le 10^5$，$1\le u,v\le n$，$1\le w\le 10^4$，输入保证任意两点都能互相到达。

思路

这道题其实就是$Party$这道题，就是一道最短路。

唯一不同的地方就是，这道题直接规定了邮局在位置$1$，那我们就把起点的位置设为$1$（即$p=1$），就可以了。

代码

#include<queue> #include<cstdio> #include<cstring> #include<iostream> using namespace std; struct node{ int to, next, x; }e1[100001], e2[100001]; int n, m, p, x, y, z, ans, le1[1001], le2[1001], k, dis1[1001], dis2[1001]; bool in[1001]; queue<int>q; int main() { memset(dis1, 0x7f, sizeof(dis1));//初始化 memset(dis2, 0x7f, sizeof(dis2)); scanf("%d %d", &n, &m);//读入 p = 1;//邮局的位置是1 for (int i = 1; i <= m; i++) { scanf("%d %d %d", &x, &y, &z);//读入 e1[++k] = (node){y, le1[x], z}; le1[x] = k;//建图 e2[k] = (node){x, le2[y], z}; le2[y] = k;//反方向建图 } q.push(p); in[p] = 1; dis1[p] = 0; while (!q.empty()) {//正向spfa int now = q.front(); q.pop(); for (int i = le1[now]; i; i = e1[i].next) { int y = e1[i].to; if (dis1[now] + e1[i].x < dis1[y]) { dis1[y] = dis1[now] + e1[i].x; if (!in[y]) { in[y] = 1; q.push(y); } } } in[now] = 0; } q.push(p); in[p] = 1; dis2[p] = 0; while (!q.empty()) {//反向spfa int now = q.front(); q.pop(); for (int i = le2[now]; i; i = e2[i].next) { int y = e2[i].to; if (dis2[now] + e2[i].x < dis2[y]) { dis2[y] = dis2[now] + e2[i].x; if (!in[y]) { in[y] = 1; q.push(y); } } } in[now] = 0; } for (int i = 1; i <= n; i++) if (i != p) ans += dis1[i] + dis2[i];//找到路径最长的一个点 printf("%d", ans);//输出 return 0; }