$$Party$$

题目链接：$jzoj1328$ / $luoguP1821$

题目

$N$头牛要去参加一场在编号为$x(1<=x<=n)$的牛的农场举行的派对$(1<=N<=1000)$,有$M(1<=m<=100000)$条有向道路，每条路长$t_i(1<=t_i<=100);$

每头牛都必须参加完派对后回到家，每头牛都会选择最短路径，求这$n$个牛的最短路径（一个来回）中最长的一条的长度。

特别提醒：可能有权值不同的重边。

输入

第$1$行： $N,M,X$；

第$2\sim m+1$行: $A_i,B_i,T_i,$ 表示有一条从 $A_i$ 到 $B_i$ 的路，长度为 $T_i.$

输出

最长最短路的长度。

样例输入

4 8 2 1 2 4 1 3 2 1 4 7 2 1 1 2 3 5 3 1 2 3 4 4 4 2 3

样例输出

10

样例解释

思路

这道题是一道最短路。

我们可以按它的要求建一个图，然后在把所有的边反向再建一个图。 然后我们把这两个图都跑一次$spfa$（不要管$spfa$死了没，用就完事了），以它们开派对的地方$x$作为起点。 我们$spfa$之后，就枚举每一个点，算出这个点的最短路径，找出最短路径最长的那一个点，记录下这个点的最短路径。

至于一个点的最短路径怎么弄，就是正向的图由起点$x$到这一个点的最短路径，再加上反向的图由起点$x$到这一个点的最短路径。其实就是走过去再走回来。

其实好像就没什么其他的了，唯一可能要注意的就是要输出的不是所有人所需最短路径的总和，而是最短路径最长的那个人的最短路径。

代码

#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 %d", &n, &m, &p);//读入 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);//正向spfa in[p] = 1; dis1[p] = 0; while (!q.empty()) { 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);//反向spfa in[p] = 1; dis2[p] = 0; while (!q.empty()) { 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 = max(ans, dis1[i] + dis2[i]);//找到路径最长的一个点 printf("%d", ans);//输出 return 0; }