AT_arc089_c.[ARC089E] GraphXY
NOI/NOI+/CTSC
通过率:0%
AC君温馨提醒
该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
给出一个A×B的矩阵,其中第i行第j列元素为di,j。试构造一个有向图,满足:
1、有向图点数≤300;
2、图中没有自环和重边;
3、图中边有边权,边权为 [0,100] 中的整数,或者是未知数X或Y;
4、对于所有x∈[1,A],y∈[1,B],满足当未知数X=x,Y=y时,图中S到T的最短路为dx,y。
输入格式
第一行两个正整数A,B(1≤A,B≤10)
接下来一个A×B的矩阵描述d。保证对于∀i∈[1,A],j∈[1,B],di,j∈[1,100]
输出格式
如果不存在满足条件的有向图,输出一行Impossible
否则第一行输出Possible,第二行输出有向图的点数n和边数m,接下来m行每行输出u,v,x描述一条从u到v、边权为x的有向边,最后一行两个正整数S,T。
输入输出样例
输入#1
2 3 1 2 2 1 2 3
输出#1
Possible 3 4 1 2 X 2 3 1 3 2 Y 1 3 Y 1 3
输入#2
1 3 100 50 1
输出#2
Impossible
输入解题思路,AI测评打分。不知道怎么写?