当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

3238:In A Crazy City

题目描述
I live in a crazy city full of crossings and bidirectional roads connecting them. On most of the days, there will be a celebration in one of the crossings, that’s why I call this city crazy.

Everyday, I walk from my home (at crossing s) to my office (at crossing t). I don't like crowds, but I don't want to waste time either, so I always choose a shortest path among all possible paths that does not visit the crossing of the celebration. If no such path exists, I don’t go to work (it’s a good excuse, isn’t it)!

In order to analyze this “celebration effect” in detail, I need n pairs of values (li, ci), where li is the length of the shortest path from crossing s to crossing t, not visiting crossing i, ci is the number of such shortest paths (not visiting crossing i). Could you help me? Note that if I can’t go to work when celebration is held at crossing i, define li = ci = 0. This includes the case when there is no path between s and t even if there’s no celebration at all.

Ah, wait a moment. Please don’t directly give me the values - that’ll drive me crazy (too many numbers!). All I need is finding some interesting conclusions behind the values, but currently I’ve no idea what exactly I want.

Before I know what you should calculate, please prove that you can indeed find all the pairs (li, ci) by telling me the value of f(x) = (l1+c1x+l2x2+c2x3+l3x4+c3x5+…+lnx2n-2+cnx2n-1) mod 19880830, for some given x.
输入解释
There will be at most 20 test cases. Each case begins with 5 integers n, m, s, t, q (1 <= s,t <= n <= 100,000, 0 <= m <= 500,000, 1 <= q <= 5). n is the number of crossings, m is the number of roads and q is the number of queries. s and t are different integers that represent my home and office, respectively. Each of the following m lines describes a road with three integers: u, v, w (1 <= u,v <= n, 1 <= w <= 10,000), indicating a bidirectional road connecting crossing u and crossing v, with length w. There may be multiple roads connecting the same pair of crossings, but a road cannot be connecting a crossing and itself. The next line contains q integers xi (1 <= xi <= 109). The last test case is following by five zeros, which should not be processed.
输出解释
For each test case, print the case number and q integers f(x1), f(x2), …, f(xq) separated by a single space between consecutive items, on one line. Print a blank line after the output of each test case.
输入样例
4 5 1 4 2
1 2 1
1 3 1
2 4 2
3 4 3
1 4 4
1 10
3 2 1 3 1
1 2 12
2 3 2
1
0 0 0 0 0
输出样例
Case 1: 10 132400

Case 2: 0

提示
Explanation

In the first sample, l1 = c1 = 0, l2 = 4, c2 = 2, l3 = 3, c3 = 1, l4 = c4 = 0. In the second sample, everything is zero.
来自杭电HDUOJ的附加信息
Recommend chenrui

该题目是Virtual Judge题目,来自 杭电HDUOJ

源链接: HDU-3238

最后修改于 2020-10-25T23:01:32+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
10000/5000MS(Java/Others) 32768/32768K(Java/Others)