## SAC '22 Code Challenge 4 Junior P5 - Obligatory Output Only Problem

View as PDF

Points: 10
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type

After constructing the best data, Max asked Wesley to test the problem.

Wesley submitted the following solution and showed Max that his data were weak (after commenting the code below):

// Dijkstra's shortest path algorithm with vertex 1 as the source
// Function Arguments:
//   adj: an adjacency list representation of a 1-indexed graph, with each edge represented by a pair (to, weight)
// Return Value: a vector containing the shortest distance from vertex 1 for each vertex, or LLONG_MAX if no path exists
vector<long long> dijkstra(const vector<vector<pair<int, long long>>> &adj) {
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
d[1] = 0;
pq.emplace(d[1], 1);
int counter = 0;
while (!pq.empty()) {
long long dv = pq.top().first;
int v = pq.top().second;
pq.pop();
// if (dv > d[v]) {
//   continue;
// }
for (auto &&edge : adj[v]) {
counter++;
int to = edge.first;
long long weight = edge.second;
if (d[to] > d[v] + weight) {
d[to] = d[v] + weight;
pq.emplace(d[to], to);
}
}
}
return d;
}


Max asked Wesley for a test case that caused this solution to TLE, but Wesley refused, so Max asked you.

Generate a graph that causes this implementation of Dijkstra's for the Single Source Shortest Path Problem to have the variable counter exceed .

Can you strengthen the test data before the contest?

#### Constraints

There are no duplicate edges.

#### Output Specification

Output the number of nodes in the graph, , and the number of edges in the graph, , on the first line.

For the next lines, output an undirected edge from to with a weight of .

#### Sample Output

5 3
1 2 5
1 3 7
1 5 2

#### Explanation for Sample Output

This solution has and . Note that this solution does not receive AC since it does not cause the above implementation to exceed the counter constraints.