题意:给定一个n个节点m条边的图,(n,m<=2000)(这道题口是心非,就当n,m<=104吧),每条边的长度∈[0,105],求1->求1->n的最短路共有几条。如果有无数条输出-1.

分析:要求最短路的条数,首先肯定要求最短路的长度,再思考最短路的条数能否在求长度的同时求出。

考虑较为稳定的heap+dijkstra算法求最短路。分析该算法求出源点到每个节点的最短路长度的过程,不难发现,在扩展每个节点的同时,将到达这个节点的最短路条数按照以下策略添加到下一个节点中即可。

1.ways[v]=ways[u] (dist[v]==dist[u]+edge[u,v])

2.ways[v]+=ways[u] (dist[v]>dist[u]+edge[u,v])

注意到边的长度可以为0,所以如果一条长度为0的边出现在最短路上,最短路就会有无数条。所以这里可以用ways[u]=-1表示有无数条最短路。

所以上面的两个式子可以进行更改,令-1=+∞,由于+∞+x=+∞:所以特判出现-1的情况即可。如下情况ways[v]=-1:

如果 dist[v]==dist[u]+edge[u,v]

1.ways[v]=-1 (edge[u,v]==-1)

2.ways[v]=-1 (ways[u]==-1)

3.ways[v]=-1 (ways[v]==-1)

如果 dist[v]>dist[u]+edge[u,v]

1.ways[v]=-1 (edge[u,v]==-1)

2.ways[v]=-1 (ways[u]==-1)

这样就可以在O(nlogn)的时间复杂度内求解本题。