[ICPC 2021 Macao R] Shortest Path Fast Algorithm

Luogu

IDLGP9659

Time1000ms

Memory256MB

DifficultyP6

2021提交答案Special JudgeO2优化构造ICPC澳门

Recently, BaoBao has learned the Shortest Path Fast Algorithm (SPFA, or more formally, Bellman-Ford-Moore Algorithm) to solve the shortest path problem efficiently. He realizes that the algorithm looks so similar to the Dijkstra's algorithm after replacing the FIFO queue with priority queue, and shows you the below pseudo code. ![](https://cdn.luogu.com.cn/upload/image_hosting/yunmac9g.png) By picking the best vertex from $Q$ we mean picking the vertex with the smallest priority value (in case that multiple vertices have the smallest priority value, pick the vertex with the largest index among them). You, the future computer scientist, find the BaoBao-modified SPFA algorithm works so slow in some carefully construted graph. However, BaoBao is sure that his algorithm works well, unless you show him a simple undirected graph that makes the variable $\tt{cnt}$ in the SPFA function no less than a certain $k$ $\textbf{at some time}$. For convenience, the source vertex of the SPFA function is specified to be vertex $1$. Just teach him a lesson! ## Input There is only one test case in each test file. The first and only line of the input contains a single integer $k$ where $k = 1$ for the sample test case and $k = 10^5$ for the only secret test case. ## Output Output several lines in the following format to describe the input data of a simple undirected graph that makes the variable $\tt{cnt}$ in the SPFA function no less than $k$ $\textbf{at some time}$. The first line contains two integers $n$ ($1 \le n \le 100$) and $m$ ($0 \le m \le 10^3$), indicating the number of vertices and edges in the graph. Then $m$ lines follow, the $i$-th of which contains three integers $u_i$, $v_i$ ($1 \le u_i, v_i \le n$) and $w_i$ ($1 \le w_i \le 10^6$), indicating that the $i$-th edge in the graph has a weight of $w_i$ and connects the $u_i$-th and the $v_i$-th vertices. Note that a simple graph contains no self-loops and no multiple edges. [samples] ## Note For your convenience, you can copy the $\tt{C++}$ code, which corresponds to the given pseudo code, from the contest website. Save the code as $\tt{spfa.cpp}$, use $\text{g++ spfa.cpp -O2 -o spfa}$ to compile it and you will get an executable file named $\tt{spfa}$. Run $\tt{spfa}$, feed your output to its standard input and it will print out the $\textbf{final}$ value of $\tt{cnt}$. Given the sample output it will print out $4$, which means the sample output is not sufficient to pass the secret test case. Note that the given code does not check the validity of your output (for example it does not check if your output is really a simple graph). You might still fail the test if your output is invalid, even if the executable prints out a large value.

Samples

Input #1

Output #1

API Response (JSON)

{
  "problem": {
    "name": "[ICPC 2021 Macao R] Shortest Path Fast Algorithm",
    "description": {
      "content": "Recently, BaoBao has learned the Shortest Path Fast Algorithm (SPFA, or more formally, Bellman-Ford-Moore Algorithm) to solve the shortest path problem efficiently. He realizes that the algorithm look",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9659"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Recently, BaoBao has learned the Shortest Path Fast Algorithm (SPFA, or more formally, Bellman-Ford-Moore Algorithm) to solve the shortest path problem efficiently. He realizes that the algorithm look...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments