UVa OJ Board

I have algorithm like LittleJohn. My program pass all Waterloo tests. I know that one test has more then n people. I tried three ways: 1. read n for i = 1 to n read human read line until empty line 2. read integer (n, dummy line) n = 0 read human; n++; until empty line 3. specification All three met...

Krzysztof, I understand you algorithm with a starting set of all nodes with firestations before launching dijkstra. so what was the error that caused your program to be Not accepted previously? Because if #fs = 0 then for all vertex dist. from firestation to it was infinity and '1' was written and ...

OK. Output belongs to Even is correct. At last I've got ACCEPTED. My algorithm is almost good. It produced bad solutions for m = 0. For this case you can find solution in time O(E) and overall O(ElogV). In spite of that, my program has O(VElogV) complexity because there was less modification to crea...

My program write the same output. But I'm given WA.

Output: Warning. My program is not ACCEPTED.

Sorry, no lowest but highest. Find max in array of dist. Normally we use Dijksta with one vertex (source) and dist for this vertex is 0. In this case we use Dijkstra with a set (set of firestations) and for all vertex from this set dist is 0. Now you must launch Dijksta. After it max := -1; for all ...

To Hongping.

You needn't iterate through all possible intersection.
Initially, you can put all firestations to heap and run Dijkstra.
Than find the intersection with the lowest distance.
Time Complexity O(E*logV).

2 2
1
2

my output is 1.

Let l = length of N = O(log(N))
The complexity of this your algorithm is O(N) = O(10^l).

I'm sure. Last year there was a contest in Poland. One of problem was the same meaning and I got ACCEPTED.

I solved this problem but I got WA.
I used Dijkstra and set all cities with fire station on 0, others on infinity.
Could you help me? Maybe a trick?