# [算法练习]洛谷P1608 路径统计（SPFA最短路计数）

SPFA，为了保证不会重复计算，需要维护一个当前队列中到这些顶点的次数，每次出队时清零。

``````// luogu-judger-enable-o2
#includebits/stdc++.h
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
const int nmax = 4e6+7;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const ull p = 67;
const ull MOD = 1610612741;
int n, m, tot;
int mp[2005][2005];
int inque[nmax];
struct edge{
int to, nxt, w;
}e[nmax1];
void add_edge(int u, int v, int w) {
e[tot].to = v;
e[tot].w = w;
}
void spfa(int s) {
for(int i = 1; i = n; ++i) {
dist[i] = i == s? 0 : INF;
inque[i] = false;
}
queueint q;
q.push(s);
inque[s] = true;
thiscnt[s] = cnt[s] = 1;
while(!q.empty()) {
int u = q.front();
q.pop();
inque[u] = false;
if(u == n)
continue;
for(int v = 1; v = n; ++v) {
if(u == v || mp[u][v] == 0)
continue;
if(dist[v]  dist[u] + mp[u][v]) {
dist[v] = dist[u] + mp[u][v];
cnt[v] = thiscnt[v] = thiscnt[u];
if(!inque[v]) {
inque[v] = true;
q.push(v);
}
} else if(dist[v] == dist[u] + mp[u][v]) {
cnt[v] += thiscnt[u];
thiscnt[v] += thiscnt[u];
if(!inque[v]) {
inque[v] = true;
q.push(v);
}
}
}
thiscnt[u] = 0;

}
}
//void dijkstra(int s) {
//
//}
int main() {
scanf("%d %d",n, m);
int u, v, w;
for(int i = 1;i = m; ++i) {
scanf("%d %d %d", u, v, w);
if(mp[u][v] == 0)
mp[u][v] = w;
else
mp[u][v] = min(mp[u][v], w);
}
spfa(1);
if(dist[n] == INF) {
} else {
printf("%d %d\n", dist[n], cnt[n]);
}
return 0;
}
``````