strawgoH

Special Judge 提交数: 29, 通过率: 6.9%, 平均分: 60.69

题目描述:

众所周知,strawgoH是一所著名的魔法学校。

strawgoH有\(N\)间教室,对于任意两间教室\(u, v\),有一条有向走廊连接它们,且通过时间为\(w_{u, v}\),注意不一定有\(w_{u, v} = w_{v, u}\)。

你并不知道经过每条走廊所需要的时间\(w_{u, v}\)是多少,但是你知道,作为一所魔法学校,strawgoH比NJU要高明多了,strawgoH的教室/走廊满足以下两个神奇的性质:

  • 路径无关:在strawgoH, 迷路是非常常见的事情。所以对于任意两间教室\(u\)和\(v\),从\(u\)走到\(v\)的时间是路径无关的。即保证不论你走什么路径(可以包含环),最终所经过的时间只取决于起点和终点是什么。当然这就要求经过某些走廊所需要的时间是负数,但是这又有什么做不到的呢?
  • 时间限制:学生们往往要在课间从一间教室赶到另一间教室。strawgoH有\(M\)个课间,第\(i\)个课间里有学生要从教室\(u_i\)走到教室\(v_i\),strawgoH需要保证你一定能在\(t_i\)时间内走到。

现在你要从教室\(s\)走到教室\(t\),问在满足以上两个条件的所有可能的情况下,从\(s\)到\(t\)的时间最久可能是多久? (因为第一个性质,这个时间是路径无关的)

或者请判断这个时间其实没有上界。

显然是一定可以从\(s\)走到\(t\)的,只要\(\forall i, j, w_{i, j} = 0\)就行了。

输入格式:

第一行两个整数\(N\)和\(M\),分别表示教室的数量和课间的数量。

接下来\(M\)行,每行三个整数\(u_i, v_i, t_i\),表示从\(u_i\)到\(v_i\)的时间小于等于\(t_i\)。

最后一行两个整数\(s\)和\(t\),表示你要从\(s\)走到\(t\)。

\(2 \le N \le 1000\)

\(0 \le M \le N^2\)

\(1 \le s, t, u_i, v_i \le N\)

\(0 \le t_i \le 10000\)

\(s \neq t\)

输出格式:

如果时间没有上界,请输出一个整数\(-1\)。否则

第一行一个整数表示从\(s\)到\(t\)需要的时间的上界\(d\)。

接下来输出一种方案使得从\(s\)到\(t\)的时间达到上界\(d\),且符合题目两个要求。

方案共\(N\)行,每行\(N\)个数字,第\(i\)行第\(j\)个数字表示通过连接\(i, j\)的走廊的时间\(w_{i, j}\)。

请保证\(\forall i, w_{i, i} = 0, \forall i, j, |w_{i, j}| \le 10^9\).

如果有多种方案,请输出任意一种

样例输入:

3 3
1 2 1
2 3 1
1 3 3
1 3

样例输出:

2
0 1 2
-1 0 1
-2 -1 0

提示:

样例2:

inupt

2 0

1 2

output

-1

时间限制: 2000ms
空间限制: 256MB

来源: by Massimo