- 题目1423：Construct The Graph
Given one weighted unidirectional graph and two nodes S and T , it is easy to know how many possible shortest paths from S to T. Now you are given W, the number of possible shortest paths, can you construct one unidirectional graph and the S and T satisfied the following conditions?
(1) The number of node of the graph must no larger than 100 and strictly larger that 0;
(2) The number of edge of the graph must no larger than 300;
(3) All nodes are identified by number from 1 to N where N is the number of node;
(4) The shortest path must no larger than 100;
(5) Exactly W shortest paths can be find from S to T.
There may exists may solutions, output any if possible.
The first line is one integer T indicates the number of the test cases. (T <= 500)
Then for every case, the first line has only one integer W, indicating the number of all shortest path from S to T.(0≤W≤2^60 )
If such graph exists, output "YES" in one single line.
Then output N M S T in a single line. (1≤S,T≤N, S!=T)
Then follows M lines:
X Y Z, indicating that there is one edge from X to Y whose weight is Z.
Otherwise output "NO" in a single line.
3 0 2 8
YES 2 0 1 2 YES 3 3 1 3 1 2 3 2 3 4 1 3 7 YES 4 6 1 4 1 2 1 1 2 1 2 3 1 2 3 1 3 4 1 3 4 1