#P18464. Graph Race
Graph Race
Graph Race
给定一张有 个顶点、 条边的无权、无向、连通图。每个顶点 都有两个整数 。
对于每个与顶点 之间有边相连的顶点 ,求
$$\max_{\substack{1\le u\le n\\u\ne v}}\{a_u-b_u\cdot\operatorname{dist}(u,v)\},$$其中 表示图中 之间的最短路径所包含的边数。
只有与顶点 直接相邻的顶点需要输出答案,但是最大值中的 可以是图中的任意其它顶点,包括顶点 ;必须排除 。
输入格式
第一行包含两个整数 (,),分别表示顶点数和边数。
接下来 行,第 行包含两个整数 ()。
接下来 行,每行包含两个整数 (,),表示一条连接 的无向边。
保证图连通,且没有重边。输入只有一组图;顶点编号从 开始。 可以为 。
输出格式
将所有与顶点 相邻的顶点 按顶点编号从小到大排列,依次输出各自的上述最大值,每个答案占一行。
答案可能为负数;请使用足够宽的有符号整数类型。
完整原样例
5 4
0 0
1 1
1 1
5 1
100 40
4 1
1 2
1 3
4 5
3
3
60