﻿ 次短路 - 鸿网互联

# 次短路

POJ 3463 - Sightseeing http://acm.pku.edu.cn/JudgeOnline/problem?id=3463 求最短路和比最短路多一的路的个数 主体还是dijkstra。其实dijkstra有种动态规划的味道，仔细理解一下然后动态规划出次短路的长以及个数 开数组d[n][2]，cnt[n][2]。[0]表示最短

### POJ 3463 - Sightseeing

http://acm.pku.edu.cn/JudgeOnline/problem?id=3463

1??len < d[v][0]

len为新的最短路长 如果d[v][0]已经有值， 把这个值赋给次短路。

2??len == d[v][0]

3??len < d[v][1]

len为新的次短路长

4??len == d[v][1]

```#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
typedef long long ll;
const int maxn = 1007, maxm = 10007;
const int INF = 0x3f3f3f3f;
struct edge{
int v, nxt, w;
}e[maxm];
int head[maxn], vis[maxn][2], cnt[maxn][2], n, cur = 0;
int d[maxn][2];
int st, ed;
struct state{
int flag, dis, node;
state(){}
state(int a, int b, int c):flag(a), dis(b), node(c){}
bool operator < (const state& S)const{
return dis > S.dis;
}
};
void addedge(int u, int v, int w){
e[cur].v = v;
e[cur].w = w;
}
void dijkstra(int st){
memset(d, INF, sizeof(d));
memset(vis, 0, sizeof(vis));
memset(cnt, 0, sizeof(cnt));
d[st][0] = 0;
cnt[st][0] = 1;
priority_queue<state> Q;
state seed(0, 0, st);
Q.push(seed);
while(!Q.empty()){
state tmp = Q.top();
Q.pop();
int flag = tmp.flag, dis = tmp.dis, u = tmp.node;
if(vis[u][flag])
continue;
vis[u][flag] = 1;
for(int i = head[u]; ~i; i = e[i].nxt){
int v = e[i].v, w = e[i].w, len = w + dis;
if(len < d[v][0]){
if(d[v][0] != INF){
d[v][1] = d[v][0];
cnt[v][1] = cnt[v][0];
state newst(1, d[v][1], v);
Q.push(newst);
}
d[v][0] = len;
cnt[v][0] = cnt[u][flag];
state newst(0, d[v][0], v);
Q.push(newst);
}
else if(len == d[v][0]){
cnt[v][0] += cnt[u][flag];
}
else if(len < d[v][1]){
d[v][1] = len;
cnt[v][1] = cnt[u][flag];
state newst(1, d[v][1], v);
Q.push(newst);
}
else if(len == d[v][1]){
cnt[v][1] += cnt[u][flag];
}
}
}
}
int main(){
int t;
scanf("%d", &t);
while(t--){
cur = 0;
int m;
scanf("%d%d", &n, &m);
while(m--){
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
}
scanf("%d%d", &st, &ed);
dijkstra(st);
int ans = cnt[ed][0];
if(d[ed][1] == d[ed][0] + 1){
ans += cnt[ed][1];
}
printf("%d\n", ans);
}
return 0;
}```

<