UOJ

1. 输入 $X$ 对于源程序 $A$ 一定不会出现超出时间限制（TLE）的问题。
2. 输入 $X$ 一定会导致源程序 $B$ 产生超出时间限制的问题。

子任务

13$107$SSSPModifiedDijkstraFloydWarshall
27$2222$SSSPFloydWarshallOptimizedBellmanFord
38$105$SSSPOptimizedBellmanFordFloydWarshall
417$157$SSSPFloydWarshallModifiedDijkstra
510$1016$SSSPModifiedDijkstraOptimizedBellmanFord
619$143$SSSPOptimizedBellmanFordModifiedDijkstra
711$3004$MysteryGamble1RecursiveBacktracking
825$3004$MysteryRecursiveBacktrackingGamble2

1. 如果未提交数据，则不得分
2. 若数据不满足输入格式要求，则不得分
3. 对源程序 $A$ 运行输入，若发生超时现象，则不得分
4. 对源程序 $B$ 运行输入，若发生超时现象，则按照前文所述的公式给出该测试点的分数。

问题 1 输入输出格式

1. $0 < V \leq 300$
2. $n_i$ 是一个非负整数
3. $0 \leq j < V$
4. $\lvert w \rvert < 10^6$
5. $0 \leq \sum_{i = 0}^{V−1} n_i \leq 5000$
6. $0 < Q ≤ 10$
7. $0 \leq s_k < V, 0 \leq t_k < V$
8. 所有询问中的起点 $s_k$ 都不能达到任何一个负权圈。

问题 1 样例

input

3
2 1 4 2 1
0
1 1 2
2
0 1
1 0



output

3
1000000000
The value of counter is: 5



问题 2 输入输出格式

1. $70 < V < 1000$
2. $1500 < E < 10^6$
3. 对于所有的边 $(a, b)$，有 $a \neq b, 0 \leq a < V, 0 \leq b < V$，不会重复描述一条边。

问题 2 样例

input

4 5
0 1
0 2
0 3
1 2
2 3



output

3
0 1 2 1
The value of counter is: 18



附录：伪代码

FloydWarshall

// pre-condition: the graph is stored in an adjacency matrix M
counter = 0
for k = 0 to V-1
for i = 0 to V-1
for j = 0 to V-1
increase counter by 1;
M[i][j] = min(M[i][j], M[i][k] + M[k][j]);
for each query p(s,t)
output M[s][t];

OptimizedBellmanFord

// pre-condition: the graph is stored in an adjacency list L
counter = 0
for each query p(s,t);
dist[s] = 0; // s is the source vertex
loop V-1 times
change = false;
for each edge (u,v) in L
increase counter by 1;
if dist[u] + weight(u,v) < dist[v]
dist[v] = dist[u] + weight(u,v);
change = true;
if change is false // this is the ’optimized’ Bellman Ford
break from the outermost loop;
output dist[t];

ModifiedDijkstra

// pre-condition: the graph is stored in an adjacency list L
counter = 0;
for each query p(s,t)
dist[s] = 0;
pq.push(pair(0, s)); // pq is a priority queue
while pq is not empty
increase counter by 1;
(d, u) = the top element of pq;
remove the top element from pq;
if (d == dist[u])
for each edge (u,v) in L
if (dist[u] + weight(u,v) ) < dist[v]
dist[v] = dist[u] + weight(u,v);
insert pair (dist[v], v) into the pq;
output dist[t];

Gamble1

Sets X = V;
labels vertex i in [0..V-1] with i;
Sets counter = 0; // will never get TLE

Gamble2

Sets X = V;
labels vertex i in [0..V-1] with i;
Sets counter = 1000001; // force this to get TLE

RecursiveBacktracking

This algorithm tries $X$ from $2$ to $V$ one by one and stops at the first valid $X$.

For each $X$, the backtracking routine label vertex $0$ with $0$, then for each vertex $u$ that has been assigned a label, the backtracking routine tries to assign the smallest possible label up to label $X-1$ to its neighbor $v$, and backtracks if necessary.

Please check RecursiveBacktracking.cpp/pas to see the exact lines where the iteration counter is increased by $1$.