Shortest Path Fast Algorithm

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.

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 cnt in the SPFA function no less than a certain $k$ at some time. For convenience the source vertex of the SPFA function is specified to be vertex $1$ .

Just teach him a lesson!

Output several lines in the following format to describe the input data of a simple undirected graph that makes the variable cnt in the SPFA function no less than $k$ 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.

#include <cstdio> #include <algorithm> using namespace std; int main(){ puts("100 165"); int inf=900000; for (int i=1;i<=99;i+=3){ printf("%d %d %d\n",i,i+1,inf); printf("%d %d %d\n",i,i+2,1); printf("%d %d %d\n",i+1,i+3,1); inf=max(1,inf/2-1); printf("%d %d %d\n",i+2,i+3,inf); printf("%d %d %d\n",i+1,i+2,1); } }

详情