AT_arc089_c.[ARC089E] GraphXY

NOI/NOI+/CTSC

通过率:0%

AC君温馨提醒

该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

给出一个A×BA \times B的矩阵,其中第ii行第jj列元素为di,jd_{i,j}。试构造一个有向图,满足:

1、有向图点数≤300\leq 300;

2、图中没有自环和重边;

3、图中边有边权,边权为 [0,100][0,100] 中的整数,或者是未知数X或Y;

4、对于所有x∈[1,A],y∈[1,B]x \in [1,A] , y \in[1,B],满足当未知数X=xX = x,Y=yY = y时,图中SS到TT的最短路为dx,yd_{x,y}。

输入格式

第一行两个正整数A,B(1≤A,B≤10)A,B(1 \leq A , B \leq 10)

接下来一个A×BA \times B的矩阵描述dd。保证对于∀i∈[1,A],j∈[1,B],di,j∈[1,100]\forall i \in [1,A] , j \in [1,B] , d_{i,j} \in [1,100]

输出格式

如果不存在满足条件的有向图,输出一行Impossible

否则第一行输出Possible,第二行输出有向图的点数nn和边数mm,接下来mm行每行输出u,v,xu,v,x描述一条从uu到vv、边权为xx的有向边,最后一行两个正整数S,TS,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测评打分。不知道怎么写?

首页