GlobeX Cup '18 S4 - Reversed Dijkstra's

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 1.0s
Memory limit: 64M

Problem types

Note that this problem has no flavourtext.

You are given an unweighted bidirectional graph with N nodes and M edges. It is guaranteed the entire graph is connected. You are also given three integers, A, B, V, and you would like to find a path from A to B with a distance d that minimizes |V-d|. However, in this path, you may not pass through any node more than once.

Input Specification

The first line will contain five space-separated integers, N, M, A, B, V\ (1 \le N \le 18, N-1 \le M \le \frac{N \times (N-1)}{2}, 1 \le A, B \le N, 0 \le V \le N-1).

The next M lines will each contain two space-separated integers, a, b\ (1 \le a, b \le N, a \ne b), indicating that node a and node b are connected by an edge. It is guaranteed there is only one edge between any 2 nodes.

Output Specification

Output a path length d that minimizes |V-d|. If there are multiple values of d, print the smallest one.


Subtask 1 [10%]

M = N-1

Subtask 2 [25%]

N \le 7

Subtask 3 [65%]

No further constraints.

Sample Input 1

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

Sample Output 1


Sample Input 2

6 6 1 5 3
1 2
2 5
1 6
6 3
3 4
4 5

Sample Output 2



There are no comments at the moment.