ABC211D Number of Shortest paths

分析

一道显然的最短路，用 dijkstra 算法。

计算最短路的同时，保存最短路个数，如果与当前最短路相同，最短路个数相加，否则到这个节点的最短路个数为上一个节点的最短路个数。

Accepted Code

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
const int mod = 1e9 + 7;
struct Edge{
	int v, nxt;
}edge[N * 2];
int head[N], vis[N], cnt;
long long num[N], dis[N];
void add_edge(int u, int v){edge[++cnt] = (Edge){v, head[u]}; head[u] = cnt;}
void dijkstra(int s)
{
    memset(dis, 0x3f3f3f3f, sizeof(dis));
    priority_queue<pair<int, int> > q;
    dis[s] = 0; num[s] = 1;
    q.push(make_pair(0, s));
    while (!q.empty())
    {
        int u = q.top().second;
        q.pop();
        if (vis[u])continue;
        vis[u] = 1;
        for (int i = head[u]; i; i = edge[i].nxt)
        {
            int v = edge[i].v;
            if (dis[v] < dis[u] + 1)continue;
            if (dis[v] == dis[u] + 1)num[v] += num[u];
            else dis[v] = dis[u] + 1, num[v] = num[u];
            num[v] %= mod;
            q.push(make_pair(-dis[v], v));
        }
    }
}
int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;
        add_edge(u, v); add_edge(v, u);
    }
    dijkstra(1);
    cout << num[n];
    return 0;
}