PKU 3463 Sightseeing
题解：求最短路以及次短路（比最短路长1）的路的条数，递推求解，四种转移
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<queue>
#include<set>
#include<math.h>
using namespace std;
#define N 1008
#define inf 0x7ffffff
struct edge {
int e, d;
edge(int a, int b) : e(a), d(b) {}
};
struct node {
int e, d, f;
node(int a, int b, int c) : e(a), d(b), f(c) {}
bool operator<(const node & a)const {
return d > a.d;
}
};
vector <edge> g[N];
int dis[N][2];
int cnt[N][2];
int n,m,s,t;
void dijkstra() {
int i, j;
priority_queue <node> q;
memset(cnt, 0, sizeof (cnt));
for (i = 0; i <= n; i++) dis[i][1] = dis[i][0] = inf;
dis[s][1] = dis[s][0] = 0;
cnt[s][0] = 1;
q.push(node(s, 0, 0));
while (!q.empty()) {
node p = q.top();
q.pop();
int k = p.e,d = p.d,f = p.f;
if (dis[k][f] != d) continue;
for (j = 0; j < g[k].size(); j++) {
int e = g[k][j].e;
int dist = g[k][j].d+d;
if ((dis[e][0] > dist)) { /*新值小于最短路*/
if (dis[e][0] != inf) {
dis[e][1] = dis[e][0];
q.push(node(e, dis[e][1], 1));
}
dis[e][0] = dist;
cnt[e][1] = cnt[e][0];
cnt[e][0] = cnt[k][f];
q.push(node(e, dist, 0));
continue;
}
if (dis[e][0] == dist) { /*新值等于最短路*/
cnt[e][0] += cnt[k][f];
continue;
}
if ((dis[e][1] > dist)) { /*新值大于最短路，小于次短路*/
dis[e][1] = dist;
cnt[e][1] = cnt[k][f];
q.push(node(e, dist, 1));
continue;
}
if (dis[e][1] == dist){ /*新值等于次短路*/
cnt[e][1] += cnt[k][f];
continue;
}
}
}
}
int main() {
int tc;
scanf("%d", &tc);
while (tc--) {
scanf("%d%d", &n, &m);
for (int i = 0; i <= n; i++)
g[i].clear();
for (int i = 0; i < m; i++) {
int a,b,c;
scanf("%d%d%d", &a, &b, &c);
g[a].push_back(edge(b, c));
}
scanf("%d%d", &s, &t);
dijkstra();
int ans = cnt[t][0];
if (dis[t][0] + 1 == dis[t][1])
ans += cnt[t][1];
printf("%d\n", ans);
}
return 0;
}