统计最短和(最短+1)路径的个数
这里把d[i][0]和d[i][1]的状态转移分开考虑,建立两个优先队列。
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 1010, M = 10010;
int n, m, S, F;
int h[N], e[M], ne[M], w[M], idx;
int dist[N][2];
bool st[N][2];
int cnt[N][2];
struct Ver
{
int id, type, dist;
bool operator> (const Ver& x) const
{
return dist > x.dist;
}
};
void add(int a, int b, int c)
{
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++ ;
}
int dijkstra()
{
memset(dist, 0x3f, sizeof dist);
memset(st, 0, sizeof st);
memset(cnt, 0, sizeof cnt);
priority_queue<Ver, vector<Ver>, greater<Ver>> q0;
priority_queue<Ver, vector<Ver>, greater<Ver>> q1;
q0.push({S, 0, 0});
dist[S][0] = 0;
cnt[S][0] = 1;
while(q0.size())
{
Ver t = q0.top();
q0.pop();
int id = t.id, type = t.type, distance = t.dist;
if(st[id][type]) continue;
st[id][type] = true;
for(int i = h[id]; ~i; i = ne[i])
{
int j = e[i];
if(dist[j][0] > distance + w[i])
{
dist[j][1] = dist[j][0], cnt[j][1] = cnt[j][0];
q1.push({j, 1, dist[j][1]});
dist[j][0] = distance + w[i], cnt[j][0] = cnt[id][type];
q0.push({j, 0, dist[j][0]});
}
else if(dist[j][0] == distance + w[i])
{
cnt[j][0] += cnt[id][type];
}
else if(dist[j][1] > distance + w[i])
{
dist[j][1] = distance + w[i], cnt[j][1] = cnt[id][type];
q1.push({j, 1, dist[j][1]});
}
else if(dist[j][1] == distance + w[i])
{
cnt[j][1] += cnt[id][type];
}
}
}
while(q1.size())
{
Ver t = q1.top();
q1.pop();
int id = t.id, type = t.type, distance = t.dist;
if(st[id][type]) continue;
st[id][type] = true;
for(int i = h[id]; ~i; i = ne[i])
{
int j = e[i];
if(dist[j][1] > distance + w[i])
{
dist[j][1] = distance + w[i], cnt[j][1] = cnt[id][type];
q1.push({j, 1, dist[j][1]});
}
else if(dist[j][1] == distance + w[i])
{
cnt[j][1] += cnt[id][type];
}
}
}
int res = cnt[F][0];
if(dist[F][0] + 1 == dist[F][1]) res += cnt[F][1];
return res;
}
int main()
{
int T;
cin >> T;
while (T -- )
{
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
for(int i = 0; i < m; i ++ )
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
}
scanf("%d%d", &S, &F);
cout << dijkstra() << endl;
}
return 0;
}