题目大意:求符合题意(三关键字)的最短路。并且算出路程最短的路径有几条、
思路:求最短路并不难,SPFA即可,关键是求总路程最短的路径条数。
我们令$h[i][j]$为$i$到$j$的最短路,$g[i][j]$为$i$到$j$的最短路条数。
$f[i][j]$的求法就是常规的Floyd求法
$g[i][j]$利用乘法原理的性质来求。
当枚举的中间点$k$满足 $f[i][k] + f[k][j] = f[i][j]$时
$g[i][j] += g[i][k] * g[k][j]$
当$f[i][k] + f[k][j] < f[i][j]$时
$g[i][j] = g[i][k] * g[k][j]$
时间复杂度 $O(kn + n^{3})$
#include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for (int i(a); i <= (b); ++i) #define dec(i, a, b) for (int i(a); i >= (b); --i) const int N = 210; int g[N][N], h[N][N], c[N], d[N], e[N], f[N], pp[N]; int n, m, s, t, x; bool inqueue[N]; string s1, s2, b[N]; map <string, int> mp; vector < pair <int, int> > v[N]; queue <int> Q; void print(int x){ if (pp[x] == 0){ cout << b[x]; return ; } else print(pp[x]); cout << "->" << b[x]; } int main(){ scanf("%d%d", &n, &m); cin >> s1; s = 1; mp[s1] = 1; c[1] = 0; b[1] = s1; rep(i, 2, n){ cin >> s2 >> x; mp[s2] = i; b[i] = s2; c[i] = x; if (s2 == "ROM") t = i; } rep(i, 1, n) rep(j, 1, n) h[i][j] = 1 << 28, g[i][j] = 0; rep(i, 1, n) h[i][i] = 0; rep(i, 1, m){ cin >> s1 >> s2 >> x; int a1 = mp[s1], a2 = mp[s2]; v[a1].push_back({a2, x}); v[a2].push_back({a1, x}); if (h[a1][a2] > x){ h[a1][a2] = h[a2][a1] = x; g[a1][a2] = g[a2][a1] = 1; } else if (h[a1][a2] == x){ ++g[a1][a2]; ++g[a2][a1]; } } rep(k, 1, n){ rep(i, 1, n){ rep(j, 1, n){ if (h[i][k] + h[k][j] == h[i][j]) g[i][j] += g[i][k] * g[k][j]; else if (h[i][k] + h[k][j] < h[i][j]){ h[i][j] = h[i][k] + h[k][j]; g[i][j] = g[i][k] * g[k][j]; } } } } memset(inqueue, false, sizeof inqueue); Q.push(s); rep(i, 1, n) d[i] = 1 << 28; rep(i, 1, n) e[i] = 1 << 28; rep(i, 1, n) f[i] = 0; d[s] = 0; e[s] = 0; f[s] = 0; rep(i, 1, n) pp[i] = 0; while (!Q.empty()){ int x = Q.front(); Q.pop(); inqueue[x] = false; for (auto u : v[x]){ int p = u.first, w = u.second; if (d[x] + w < d[p] || d[x] + w == d[p] && f[x] + c[p] > f[p] || d[x] + w == d[p] && f[x] + c[p] == f[p] && e[x] + 1 < e[p]){ d[p] = d[x] + w; f[p] = f[x] + c[p]; e[p] = e[x] + 1; pp[p] = x; if (!inqueue[p]){ inqueue[p] = true; Q.push(p); } } } } printf("%d %d %d %d ", g[s][t], d[t], f[t], f[t] / e[t]); print(t); putchar(10); return 0; }