Problem Description

In the world of competitive programming, designing a good contest is challenging, especially in creating test data that distinguishes between different programs. A well-designed test set should award full points to programs that meet all requirements and expose flaws in seemingly correct programs with specific data.

In this problem, your role is reversed! As an experienced programmer, you will assist the Problem Setting Committee of the Happy Programmer Contest in designing test data. The committee has selected two graph theory problems, divided into 8 sub-tasks. They have written several programs that seem capable of solving these sub-tasks. When designing data for a task, the committee expects some programs to score full points while others should score zero or partial points. You will receive these source programs (C, C++, Pascal versions). For each sub-task, you need to generate a dataset \( X \) that distinguishes between the two given programs \( A \) and \( B \). Specifically, the data must meet these conditions:

• Input \( X \) must not cause program \( A \) to exceed the time limit (TLE).
• Input \( X \) must cause program \( B \) to exceed the time limit.

Additionally, the committee prefers smaller datasets and hopes the data contains no more than \( T \) integers.

This problem focuses only on whether programs \( A \) and \( B \) time out, not on the correctness of results.

The committee has chosen Single Source Shortest Path (SSSP) and a problem called Mystery as the contest topics. Pseudocode for the committee's solutions is provided in the appendix, and the actual C, C++, and Pascal source codes are included in the provided files.

Sub-tasks

Refer to the table below. Each row describes a sub-task. The first six sub-tasks are related to SSSP, and sub-tasks 7 and 8 are related to the Mystery problem. The points for each task are listed in the table.

For each sub-task, your program's input \( X \) must distinguish between programs \( A \) and \( B \) to earn points. Your score is determined by the number of integers in \( X \). If \( X \) contains \( F \) integers, the sub-task's full score is \( S \), and \( T \) is the target size, then the score for this test case is given by:

\[ S \times \min\{T / F, 1\} \]

If your test data \( X \) contains no more than \( T \) integers, you will receive the full score for that task.

You need to name your 8 test datasets 1.txt to 8.txt. For each sub-task \( X \), the judging system will determine your score based on the following steps:

• If no data is submitted, no points are awarded.
• If the data does not meet the input format requirements, no points are awarded.
• If program \( A \) times out on the input, no points are awarded.
• If program \( B \) times out on the input, points are awarded according to the formula mentioned earlier.

All provided source codes maintain a counter to count program operations. If this counter exceeds \( 10^6 \) during execution, the program is considered to have timed out.

Problem 1: Single Source Shortest Path (SSSP)

Given a weighted directed graph \( G \) and two nodes \( s \) and \( t \) in \( G \), let \( p(s, t) \) be the shortest path length from \( s \) to \( t \) in \( G \). If \( s \) and \( t \) are not connected, \( p(s, t) = 10^9 \). The input is \( G \) and \( Q \) queries \( (s_1, t_1), (s_2, t_2), \ldots, (s_Q, t_Q) \). The output is the corresponding \( p(s_1, t_1), p(s_2, t_2), \ldots, p(s_Q, t_Q) \).

Problem 2: Mystery Problem

Given an undirected graph \( G \) with \( V \) nodes and \( E \) edges, assign all nodes a number (range \( [0, X-1] \)) such that all directly connected nodes have different numbers. Find the smallest \( X \) that satisfies this condition.

Input Format

Problem 1

The input data consists of two parts: the first part describes the weighted directed graph \( G \) using an adjacency list, and the second part describes the shortest path queries on \( G \).

The first part's first line contains an integer \( V \), the number of nodes in \( G \), numbered \( 0, 1, \ldots, V-1 \).

The next \( V \) lines describe each node's edges. The first integer \( n_i \) on each line is the number of outgoing edges from node \( i \), followed by \( n_i \) pairs \( (j, w) \) representing an edge from \( i \) to \( j \) with weight \( w \).

The second part's first line contains an integer \( Q \), the number of queries.

The next \( Q \) lines, each containing two integers \( s_k \) and \( t_k \), are the start and end points for each query.

Integers in each line must be separated by at least one space. Additionally, the data must meet these conditions:

• \( 0 < V \leq 300 \), \( n_i \) is a non-negative integer, \( 0 \leq j < V \), \( |w| < 10^6 \), \( 0 \leq \sum_{i=0}^{V-1} n_i \leq 5000 \), \( 0 < Q \leq 10 \), \( 0 \leq s_k < V, 0 \leq t_k < V \);
• No start node \( s_k \) in any query can reach a negative weight cycle.
• For all edges \( (a, b) \), \( a \neq b, 0 \leq a < V, 0 \leq b < V \), and no edge is described more than once.

Problem 2

The first line of input contains two integers \( V \) and \( E \).

The next \( E \) lines, each containing two integers \( a \) and \( b \), indicate that \( a \) and \( b \) are directly connected in \( G \). The input must meet these conditions:

• \( 70 < V < 1000 \), \( 1500 < E < 10^6 \);
• For all edges \( (a, b) \), \( a \neq b, 0 \leq a < V, 0 \leq b < V \), and no edge is described more than once.

Output Format

Problem 1

The program will output \( Q \) lines, each containing an integer representing \( p(s_k, t_k) \). At the end of the output, all provided programs will print the counter value for this input.

Problem 2

The program will output the smallest \( X \) on the first line, followed by \( V \) integers on the second line, describing the labels for nodes \( 0 \) to \( V-1 \). At the end of the output, all provided programs will print the counter value for this input.

Sample Input and Output

Input Sample #1

3
2 1 4 2 1
0
1 1 2
2
0 1
1 0
// For Problem 1

Output Sample #1

3
1000000000
The value of counter is: 5

Input Sample #2

4 5
0 1
0 2
0 3
1 2
2 3
// For Problem 2

Output Sample #2

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

Notes

Source codes are provided in the attachments.

Appendix: Pseudocode

Below is the pseudocode for all provided programs; the variable counter approximates the program's runtime. The judging will use the C++ versions of these pseudocodes.

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

Thanks to zhouyonglong for modifying the spj.

见题面 Input 部分

见题面 Output 部分