分析
一道显然的最短路，用 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;
}