Luogu p1608 path statistics solution

Luogu P1608 Path Statistics Answer key

Topic link ：P1608 Path Statistics

The question ：

One sentence question ： Shortest circuit count .

“RP The restaurant ” The quality of the staff is not average , After calculating the same phone number in unison , Ready to let HZH,TZY To deliver fast food , They drew a map of the city where they lived , Known on their maps , Yes $N$ A place to , And they are currently in a position marked “1” In a small town , The place of delivery is marked as “N” The town of .（ It's a bit of rubbish ） Besides, I also know that these roads are one-way , From the town $I$ To $J$ Need to spend $D[I,J]$ Time for , In order to deliver fast food to customers more efficiently and quickly , They want to take a route from the town $1$ To the town $N$ The least expensive way , But before they set out , Hit someone who was angry because of the traffic jam on the road FYY, Inspired by , You can't just know one route , In case ... therefore , They invited FYY Let's study the next question ： How many paths are there that cost the least ？

about $100\%$ The data of $1\le N\le 2000$,$0\le E\le N\times (N-1)$,$1\le C\le 10$.

The data of the shortest path meter says that it cannot be used spfa（spfa Is dead ）

set up $f_u$ From the beginning to the beginning $u$ The shortest path number of nodes

Obviously with dijkstra Brush Watch

if $(u,v)$ Relaxation succeeded , That is to say

d[v]>d[u]+w

Let's just let f[v]=f[u]

Otherwise, if

d[v]==d[u]+w

let f[v]+=f[u]

be without , That's the water

Time complexity $O(n\log m)$ , Here I write the adjacency matrix so $m\approx n^2$

Code ：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <queue>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(2e3+15)

int n,m,d[N],vis[N],f[N],g[N][N];
struct node
{
    
    int u,dis;
    bool operator<(const node &o)const
        {
    return dis>o.dis;}
};
priority_queue<node> q;
void dijkstra(int st)
{
    
    memset(d,0x3f,sizeof(d));
    d[st]=0;f[st]=1;
    q.push({
    st,0});
    while(!q.empty())
    {
    
        int u=q.top().u;q.pop();
        if(vis[u])continue;
        vis[u]=1;
        for(int v=1,w; v<=n; v++)
        {
    
            if((w=g[u][v])>=INF)continue;
            if(d[v]>d[u]+w)
            {
    
                d[v]=d[u]+w;
                f[v]=f[u];
                q.push({
    v,d[v]});
            }else if(d[v]==d[u]+w)f[v]+=f[u];
        }
    }
}   
signed main()
{
    
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            g[i][j]=INF;
    for(int i=1,u,v,w; i<=m; i++)
    {
    
        cin >> u >> v >> w;
        g[u][v]=min(g[u][v],w);
    }
    
    dijkstra(1);
    if(d[n]>=INF)cout << "No answer\n";
    else cout << d[n] << " " << f[n];
    return 0;
}

Reprint please explain the source