[ARC089E] GraphXY
题意翻译
### 题目描述
给出一个$A \times B$的矩阵,其中第$i$行第$j$列元素为$d_{i,j}$。试构造一个有向图,满足:
1、有向图点数$\leq 300$;
2、图中没有自环和重边;
3、图中边有边权,边权为 $[0,100]$ 中的整数,或者是未知数`X`或`Y`;
4、对于所有$x \in [1,A] , y \in[1,B]$,满足当未知数$X = x$,$Y = y$时,图中$S$到$T$的最短路为$d_{x,y}$。
### 输入格式
第一行两个正整数$A,B(1 \leq A , B \leq 10)$
接下来一个$A \times B$的矩阵描述$d$。保证对于$\forall i \in [1,A] , j \in [1,B] , d_{i,j} \in [1,100]$
### 输出格式
如果不存在满足条件的有向图,输出一行`Impossible`
否则第一行输出`Possible`,第二行输出有向图的点数$n$和边数$m$,接下来$m$行每行输出$u,v,x$描述一条从$u$到$v$、边权为$x$的有向边,最后一行两个正整数$S,T$。
题目描述
[problemUrl]: https://atcoder.jp/contests/arc089/tasks/arc089_c
シカのAtCoDeerくんは次のような条件を満たす有向グラフを欲しがっています。
- 頂点数$ N $は $ 300 $ 以下
- 自己ループや多重辺があってはいけない
- 頂点には $ 1 $ から $ N $ の番号が付けられている
- 各辺には $ 0 $ 以上 $ 100 $ 以下の整数値の重み、もしくは、`X` または `Y` というラベルが付けられている
- 全ての $ 1\ <\ =\ x\ <\ =\ A $, $ 1\ <\ =\ y\ <\ =\ B $, を満たす整数の組 $ (x,y) $ に対し、 ラベル `X` が付けられた辺の重みを $ x $ に、 `Y` が付けられた辺の重みを $ y $ に書き換えたグラフの 頂点 $ S $ から $ T $ への最短距離は $ d_{x,y} $
AtCoDeerくんのためにこのようなグラフ(と $ S $ と $ T $ の組)をひとつ構成してください。条件を満たすグラフが存在しない場合はそれを指摘してください。 出力の方法については出力の欄を参照してください。
输入输出格式
输入格式
入力は以下の形式で標準入力から与えられる。
> $ A $ $ B $ $ d_{1,1} $ $ d_{1,2} $ $ .. $ $ d_{1,B} $ $ d_{2,1} $ $ d_{2,2} $ $ .. $ $ d_{2,B} $ $ : $ $ d_{A,1} $ $ d_{A,2} $ $ .. $ $ d_{A,B} $
输出格式
条件を満たすグラフが存在しない場合は `Impossible` と出力せよ。
条件を満たすグラフが存在する場合、 $ 1 $ 行目に `Possible` と出力せよ。 $ 2 $行目以降に 構成したグラフを以下の形式で標準出力に出力せよ。
> $ N $ $ M $ $ u_1 $ $ v_1 $ $ c_1 $ $ u_2 $ $ v_2 $ $ c_2 $ : $ u_M $ $ v_M $ $ c_M $ $ S $ $ T $
ただし、 $ M $ は出力するグラフの辺数、 $ u_i,v_i,c_i $ はグラフの辺を表す。 これは頂点 $ u_i $ から 頂点 $ v_i $ に 重み、あるいはラベル $ c_i $ の有向辺があることを意味する。 入出力例も参考にせよ。
输入输出样例
输入样例 #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
说明
### 制約
- $ 1 $ $ <\ = $ $ A,B $ $ <\ = $ $ 10 $
- $ 1 $ $ <\ = $ $ d_{x,y} $ $ <\ = $ $ 100 $ ($ 1 $ $ <\ = $ $ x $ $ <\ = $ $ A $, $ 1 $ $ <\ = $ $ y $ $ <\ = $ $ B $)
- 入力は全て整数