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

View as PDF

Submit solution


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) {
  vector<long long> d(adj.size(), LLONG_MAX);
  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 10^7.

Can you strengthen the test data before the contest?

Constraints

1 \le N \le 10^5

0 \le M \le \min(2 \times 10^5, \frac{N \times (N-1)}{2})

1 \le u, v \le N

u \ne v

1 \le w \le 10^9

There are no duplicate edges.

Output Specification

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

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

Sample Output

5 3
1 2 5
1 3 7
1 5 2

Explanation for Sample Output

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


Comments

There are no comments at the moment.