为什么topsort对这道题不行
It has been a prosperous year for King Charles and he is rapidly expanding his kingdom.A beautiful new kingdom has been recently constructed and in this kingdom there are many cities connected by a number of one-way roads.Two cities may be directly connected by more than one roads, this is to ensure high connectivity.
In this new kingdom King Charles has made one of the cities at his financial capital and one as warfare capital and he wants high connectivity between these two capitals.The connectivity of a pair of cities say city A and city B is defined as the number of different paths from city A to city B. A path may use a road more than once if possible. Two paths are considered different if they do not use exactly the same sequence of roads.
There are N cities numbered 1 to N in the new kingdom and M one-way roads . City 1 is the monetary capital and city N is the warfare capital.
You being one of the best programmers in new kingdom need to answer the connectivity of financial capital and warfare capital ,i.e number of different paths from city 1 to city N.
Input Description:
First line contains two integers N and M.
Then follow M lines ,each having two integers say x and y, 1<=x,y<=N , indicating there is a road from city x to city y.
Output Description:
Print the number of different paths from city 1 to city N modulo 1,000,000,000(10^9).If there are infinitely many different paths print "INFINITE PATHS"(quotes are for clarity).
Sample Input:
5 5
1 2
2 4
2 3
3 4
4 5
Sample Output:
2
Sample Input:
5 5
1 2
4 2
2 3
3 4
4 5
Sample Output:
INFINITE PATHS
Constraints:
2<=N<=10,000(10^4)
1<=M<=1,00,000(10^5)
Two cities may be connected by more than two roads and in that case those roads are to be considered different for counting distinct paths
题目大意：
N个城市由M条路相连（有向路），两个城市之间有可能多条路相连，这些路被认为是不同的。求从第1个城市到第N个城市有多少条不同的路相连。
分析：由于每条路可以走多次，如果经过的路中有环的话，就是INFINITE PATHS。
第一步：找到从1出发达到的结点，只有这些结点对结果有影响。如果不能到达N，直接为0
第二步：在这些结点中做topsort。对结果分两种情况：
1， 1和N都在topsort的结果中。
设定count[1] = 1,其他为0
按照topsort的顺序，对到达结点u的路条数设定为count[u] += count[pre_u] * road[pre_u][u]
pre_u是出现在topsort中u前面并且有路径到达u的结点，road[pre_u][u] 是pre_u到u的路条数。
2， 1和N有一个不在topsort结果中。
1和N之间至少有一个环，而且1和N是相通的，所以为INFINITE PATHS
但是，提交的结果是WR，说明还有反例。
[解决办法]
有时理解别人的思路确实不容易，没搞明白路径统计那块的情况，我的思路就是利用类似spfa的方法，从起点到该点的路径数量 = 所有父节点路径数量的和。
