CF 660 C. Uncle Bogdan and Country Happiness

题目链接

C. Uncle Bogdan and Country Happiness

题目概述

初始时每个人都在标号为1的城市,然后回到每个人各自的城市,选择从起点到终点的最短路径,相邻城市之间的距离一样,每个人在进入一个城市时可以改变他的心情,从Good变为Bad,但是不可以从Bad变成Good,每个人进入一个城市时他的心情会影响这个城市的幸福指数,如果是Good那么指数加一否则减一,在城市里面心情是不会改变的,现在给出一种城市幸福指数的可能性,计算有没有可能得到这种幸福指数格局?

数据规模:

[1leq t leq 10000, 1leq n leq 10^5, 0leq mleq 10^9leq p_i leq m, sum_{i=1}^{n}p_i = m-10^9 leq h_i leq 10^9 , i=1,2,3dots,n.
]