2014
03-09

# 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.

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.

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

HintExplanation

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. 

1. #include <stdio.h>
int main(void)
{
int arr[] = {10,20,30,40,50,60};
int *p=arr;
printf("%d,%d,",*p++,*++p);
printf("%d,%d,%d",*p,*p++,*++p);
return 0;
}

为什么是 20,20,50,40,50. 我觉得的应该是 20,20,40,40,50 . 谁能解释下？