题目描述：
你在一个城市里，城市由 n 个路口组成，路口编号为 0 到 n - 1 ，某些路口之间有 双向 道路。输入保证你可以从任意路口出发到达其他任意路口，且任意两个路口之间最多有一条路。
给你一个整数 n 和二维整数数组 roads ，其中 roads[i] = [ui, vi, timei] 表示在路口 ui 和 vi 之间有一条需要花费 timei 时间才能通过的道路。你想知道花费 最少时间 从路口 0 出发到达路口 n - 1 的方案数。
请返回花费 最少时间 到达目的地的 路径数目 。由于答案可能很大，将结果对 109 + 7 取余 后返回。
数据范围：
$1\le n \le 200, 1\le time_i \le 10^9$
题解：
dijkstra 求最短路径方案数，本质就是利用三角不等式更新的时候，更新一下路径条数。
如果 $dis[v] = dis[u] + w$ ，则 $cnt[v] = cnt[v] + cnt[u]$ 。
如果 $dis[v] \gt dis[u] + 2$ ， 则 $cnt[v] = cnt[u]$ 。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const static long long mod = 1e9 + 7;
const long long INF_LL = 0x3f3f3f3f3f3f3f3f;
const int INF = 0x3f3f3f3f;
vector<long long> dis;
vector<int> cnt;
vector<vector<pair<int, int>>> g;
vector<bool> vis;
int countPaths(int n, vector<vector<int>> &roads)
{
g.resize(n);
vis.resize(n);
cnt.resize(n);
dis.resize(n, INF_LL);
for (auto &edge : roads)
{
int u = edge[0], v = edge[1], w = edge[2];
g[u].emplace_back(v, w);
g[v].emplace_back(u, w);
}
priority_queue<pair<long long, int>> q;
q.push({0, 0});
dis[0] = 0;
cnt[0] = 1;
while (q.size())
{
auto out = q.top();
q.pop();
int u = out.second;
if (vis[u])
continue;
vis[u] = true;
if (u == n - 1)
break;
for (int i = 0; i < g[u].size(); ++i)
{
int v = g[u][i].first, w = g[u][i].second;
if (dis[v] > dis[u] + w)
{
dis[v] = dis[u] + w;
cnt[v] = cnt[u];
q.push({-dis[v], v});
}
else if (dis[v] == dis[u] + w)
{
cnt[v] = (cnt[v] + cnt[u]) % mod;
}
}
}
cout << dis[n - 1] << ", " << cnt[n - 1] << endl;
return cnt[n - 1];
}
};
|