九度Online Judge

OJ新增积分机制,如有任何问题或者建议,请发帖到九度论坛OJ意见反馈版,祝大家一切顺利!
亲,九度OJ官方微博开通了,欢迎你来粉!微博地址:weibo.com/jobdu

 题目1423-九度Online Judge,用代码记录你的成长之路!

题目1423:Construct The Graph

时间限制:1 秒

内存限制:32 兆

特殊判题:

提交:176

解决:71

题目描述:

        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. (1S,TN, S!=T)

 Then follows M lines:

 X Y Z, indicating that there is one edge from X to Y whose weight is Z.

 (1X,YN,X!=Y,0<Z100)

        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
来源:
第四届ACM_DIY群程序设计竞赛