真正的最短路计数问题

这道题就是传说中的最短路计数问题了。

其实最短路计数就是在最短路算法上面添加两句话就完事了。

一句是在判断有道路与当前最短路一样长的时候，答案会变多。

一句是在更新最短路的时候，答案会变成从那个点开始的最短路。

所以就没有问题了？

这道题不仅有重边，还可能后面给你更小的边！

解决方法有两个：

1. 乖乖用邻接矩阵，写一下基于矩阵的dijkstra。

2. 用个邻接矩阵来判断下边的关系，看看有相同起点终点的边是否需要加进来。再换成邻接表跑堆优化的dijkstra。

我用的是第二种。我不会写矩阵的算法除了floyd。

代码：

#include
    
     #include
     
      #include
      
       const int maxn = 2005;struct Edges{    int next, to, weight;} e[4000005];int b[maxn][maxn];int head[maxn], tot;int dist[maxn];int cnt[maxn];int n, m;struct Heapnodes{    int d, u;    bool operator < (const Heapnodes &rhs) const    {        return d > rhs.d;    }};int read(){    int ans = 0, s = 1;    char ch = getchar();    while(ch > '9' || ch < '0'){ if(ch == '-') s = -1; ch = getchar(); }    while(ch >= '0' && ch <= '9') ans = ans * 10 + ch - '0', ch = getchar();    return s * ans;}void link(int u, int v, int w){    e[++tot] = (Edges){head[u], v, w};    head[u] = tot;}void dijkstra(){    memset(dist, 0x3f, sizeof dist);    std::priority_queue
       
         heap;    dist[1] = 0; heap.push((Heapnodes){dist[1], 1});    cnt[1] = 1;    while(!heap.empty())    {        Heapnodes x = heap.top(); heap.pop();        int d = x.d, u = x.u;        if(d != dist[u]) continue;        for(int i = head[u]; i; i = e[i].next)        {            int v = e[i].to;            if(dist[u] + e[i].weight == dist[v]) cnt[v] += cnt[u];            if(dist[u] + e[i].weight < dist[v])            {                dist[v] = dist[u] + e[i].weight;                heap.push((Heapnodes){dist[v], v});                cnt[v] = cnt[u];            }        }    }}int main(){    memset(b, 0x3f, sizeof b);    n = read(), m = read();    while(m--)    {        int u = read(), v = read(), w = read();        if(b[u][v] > w)        {            link(u, v, w);            b[u][v] = w;        }    }    dijkstra();    if(dist[n] != 0x3f3f3f3f) printf("%d %d\n", dist[n], cnt[n]);    else printf("No answer\n");    return 0;}