Problem2288--这是有多少条最短路?

2288: 这是有多少条最短路?

Time Limit: 10 Sec  Memory Limit: 32 MB
Submit: 6  Solved: 5
[Submit] [Status] [Web Board] [Creator:]

Description

一看到“最短路”这三个字,相信有大量acmer狂戳这道题,不过这还真的不是赤裸裸的最短路,还得加点规则。
题目给出一个加权的有向图,表示为一个二维矩阵,以及起点和终点,要求求出起点到终点最短路最多有多少条。需要注意的是,每条最短路是完全不同的,不重叠的,也就是说,任意两条路之间不可以有公共边。

Input

输入有多组数据,每组数据第一行有一个数n,表示矩阵大小(n*n),接下来有n行数据,下标i,j(0<=i,j<n)
表示点i到j的距离,-1表示i和j之间不通。最后一行有两个整数s,e,(0<=s,e<n)表示起点和终点。数据处理到文件尾。

Output

对于每组测试数据输出一个数字,表示起点到终点最多的不重叠的最短路的条数。如果不存在最短路,请输出“inf”。

Sample Input Copy

4
0 1 1 -1
-1 0 1 1
-1 -1 0 1
-1 -1 -1 0
0 3
5
0 1 1 -1 -1
-1 0 1 1 -1
-1 -1 0 1 -1
-1 -1 -1 0 1
-1 -1 -1 -1 0
0 4

Sample Output Copy

2
1