2886 - 最短路的最大值
题目描述
有 N 个点 M 条边构成的有向图。
现给出 X 点为目标点，除了 X 点以外，其余每个点都要以最短路走到 X 点，并以最短路从 X 点回到每个点。
请编程求出每个点以最短路往返 X 点的最大值是多少？
输入
第 1 行输入 3 个整数 N,M,X。
接下来 M 行，每行有 3 个整数 u,v,len，表示点 u,v 之间有一条边长为 len 的有向边。
输出
请输出每个点以最短路往返 X 点来回最短路和的最大值。
样例
输入
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
说明
样例 1 解释
样例 1 如下图所示。
数据范围
对于全部的测试点，保证 1 \leq x \leq n \leq 10^3，1 \leq m \leq 10^5，1 \leq u,v \leq n，1 \leq len \leq 10^2，保证从任何一个结点出发都能到达 x 号结点，且从 x 出发可以到达其他所有结点。
来源
东方博宜OJ
标签