题意：给定一个 n 个节点 m 条边的图，(n,m<=2000)(这道题口是心非，就当 n,m<=10⁴ 吧)，每条边的长度∈[0,10⁵], 求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) 的时间复杂度内求解本题。

#include <iostream>
#include <cstring>
#include <queue>
#include <cstdio>

#define MX 20001
#define mod 1000000009

using namespace std;

int u[MX],v[MX],w[MX],fst[MX],nxt[MX],lnum=-1,n,m;
int dist[MX],ways[MX],vis[MX];

void addeg(int nu,int nv,int nw)
{
    lnum++;
    u[lnum]=nu,v[lnum]=nv,w[lnum]=nw;
    nxt[lnum]=fst[nu],fst[nu]=lnum;
}

void input()
{
    int a,b,c;
    scanf("%d%d",&n,&m);
    for(int i=1; i<=m; i++)scanf("%d%d%d",&a,&b,&c),addeg(a,b,c),addeg(b,a,c);
}

priority_queue<pair<int,int> > q;

void work()
{
    int nt;
    memset(dist,0x6f,sizeof(dist)),memset(vis,0,sizeof(vis)),memset(ways,0,sizeof(ways));
    dist[1]=0,ways[1]=1;
    q.push(make_pair(0,1));
    while(!q.empty())
    {
        nt=q.top().second;q.pop();
        if(vis[nt])continue;
        vis[nt]=1;
        for(int i=fst[nt];i!=-1;i=nxt[i])
        {
            if(dist[v[i]]==dist[u[i]]+w[i])
            {
                if(w[i]==0)ways[v[i]]=-1;
                else
                {
                    if(ways[u[i]]==-1||ways[v[i]]==-1)ways[v[i]]=-1;
                    else ways[v[i]]=(ways[u[i]]+ways[v[i]])%mod;
                }
            }
            else if(dist[v[i]]>dist[u[i]]+w[i])
            {
                dist[v[i]]=dist[u[i]]+w[i];
                if(w[i]==0)ways[v[i]]=-1;
                else ways[v[i]]=ways[u[i]];
                q.push(make_pair(-dist[v[i]],v[i]));
            }
        }
    }
    cout<<ways[n]<<endl;
}

int main()
{
    memset(fst,0xff,sizeof(fst));
    input(),work();
    return 0;
}