题解与讨论区 1003: 美人鱼

题解与讨论区 1003: 美人鱼

[命题人 : ]
时间限制 : 1.000 sec  内存限制 : 128 MB

返回问题页面

题目描述

人类和人鱼拥有共同的祖先,因为某种原因发生了分化,人鱼到了大海里生活。近年来人类对大海及生态的破坏,人鱼族的生存环境受到了严重的影响。最近某地产公司筹备一个填海计划,在附近的大海中装入了声呐系统,这极大地限制了人鱼的活动。

人鱼族的居民们为了适应环境,建立了\(n\)个聚居点(从\(1\)到\(n\)编号),\(m\)条有一定长度的单向通道,每条由一个聚居点通向另一个聚居点。人鱼族派出了美人鱼珊珊去勾引地产公司的老总刘轩,来逼迫他关闭声呐系统。现在珊珊在\(S\)号点,她要到\(T\)号点,然后通过\(T\)号点到达陆地上。她当然希望自己能走最短的路来从\(S\)到达\(T\),不过比最短路长\(1\)的路径,她也是可以接受的。她想知道从S到T的最短路和比最短路长\(1\)的路径一共有多少条。


第1003题的题解