＜＜算法竞赛进阶指南＞＞: 观光(单源最短路和单源次短路计数问题)

对于单源最短路计数问题,我们已经不陌生,但是对于单源次短路计数问题可能比较陌生,那么我们接下来看一道题,

“您的个人假期”旅行社组织了一次比荷卢经济联盟的巴士之旅。

比荷卢经济联盟有很多公交线路。

每天公共汽车都会从一座城市开往另一座城市。

沿途汽车可能会在一些城市（零或更多）停靠。

旅行社计划旅途从 $S$ 城市出发，到 $F$ 城市结束。

由于不同旅客的景点偏好不同，所以为了迎合更多旅客，旅行社将为客户提供多种不同线路。

游客可以选择的行进路线有所限制，要么满足所选路线总路程为 $S$ 到 $F$ 的最小路程，要么满足所选路线总路程仅比最小路程多一个单位长度。

如上图所示，如果 $S=1，F=5$，则这里有两条最短路线 $1\to 2\to 5,1\to 3\to 5$，长度为 $6$；有一条比最短路程多一个单位长度的路线 $1\to 3\to 4\to 5$，长度为 $7$。

现在给定比荷卢经济联盟的公交路线图以及两个城市 $S$ 和 $F$，请你求出旅行社最多可以为旅客提供多少种不同的满足限制条件的线路。

输入格式
第一行包含整数 $T$，表示共有 $T$ 组测试数据。
每组数据第一行包含两个整数 $N$ 和 $M$，分别表示总城市数量和道路数量。
接下来 $M$ 行，每行包含三个整数 A,B,L，表示有一条线路从城市 $A$ 通往城市 $B$，长度为 $L$。
需注意，线路是 单向的，存在从 $A$ 到 $B$ 的线路不代表一定存在从 $B$ 到 $A$ 的线路，另外从城市 $A$ 到城市 $B$ 可能存在多个不同的线路。
接下来一行，包含两个整数 $S$ 和 $F$，数据保证 $S$ 和 $F$ 不同，并且 $S、F$ 之间至少存在一条线路。

输出格式

每组数据输出一个结果，每个结果占一行。
数据保证结果不超过 1 0 9 10^9 109。

数据范围

$2\le N\le 1000$
$1\le M\le 10000$
$1\le L\le 1000$
$1\le A,B,S,F\le N$

输入样例：

2
5 8
1 2 3
1 3 2
1 4 5
2 3 1
2 5 3
3 4 2
3 5 4
4 5 3
1 5
5 6
2 3 1
3 2 1
3 1 10
4 5 2
5 2 7
5 2 7
4 1

输出样例：

3
2

抽象出模型就是从 $S$ 出发到 $F$的单源最短路和单源次短路的计数问题,发现了其模型,解题难度就大大降低了,然后因为要求最短路和次短路, 然后计数问题的话,可以仿照最短路计数来做, 利用 $cnt$ 数组, 但是这里既要计数最短路, 又要计数次短路, 所以我们最好给 $cnt$ 数组开二维

这里会有一个问题, 我们在选择算法时,使用 $dijkstra$算法的堆优化版的话, 使用的优先队列,得利用结构体,将最短边和次短边分开

 #include using namespace std; const int N = 1010, M =  20010; int e[M],ne[M],h[N],w[M],idx; int cnt[N][2],dist[N][2]; int n,m,S,T,t; bool st[N][2]; void add(int a,int b,int c)   //建边 {     e[idx] = b;     ne[idx] = h[a];     w[idx] = c;     h[a] = idx ++; } struct Ver   //结构体存边 {     int id,type,dist;// id = 0 最短路   id  = 1 次短路     bool operator > (const Ver & W)const//重载优先队列中的排序算法     //小根堆要重载大于号, 大根堆重载小于号     {  return dist > W.dist; } }; int dijkstra() {     memset(st,false,sizeof st);   //初始化操作     memset(dist,0x3f,sizeof dist);     memset(cnt,0,sizeof cnt);     dist[S][0] = 0;  //初始化起点     cnt[S][0] = 1;   //初始化起点     priority_queue<Ver,vector<Ver>,greater<Ver>>heap;   //建立大根堆     heap.push({S,0,0});   //入队     while(heap.size())  {  Ver t = heap.top();  heap.pop();  int ver = t.id, type = t.type, distance = t.dist, count = cnt[ver][type];    if(st[ver][type]) continue;  st[ver][type] = true;    for(int i = h[ver]; i != -1; 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];     heap.push({j,1,dist[j][1]});     dist[j][0] = distance + w[i],cnt[j][0] = count;     heap.push({j,0,dist[j][0]});  }  //找到了其他的最短路      else if(dist[j][0] == distance + w[i])  cnt[j][0] += count;  // 找到了更短的次短路      else if(dist[j][1] > distance + w[i])      {   dist[j][1] = distance + w[i],cnt[j][1] = count;   heap.push({j,1,dist[j][1]});      }      // 找到了其他的次短路      else if(dist[j][1] == distance + w[i]) cnt[j][1] += count;  }     }     int res = cnt[T][0];   //最短路的方案     if(dist[T][0] + 1 == dist[T][1] ) res += cnt[T][1];      //如果最短路和次短路只相差了1 那么就加上次短路     return res; } int main() {     cin >> t;     while(t--)     {  cin >> n >> m;  memset(h,-1,sizeof h);  idx = 0;  for(int i = 1; i <= m; i ++ )  {      int a,b,c;      cin >> a >> b >> c;      add(a,b,c),add(b,a,c);  } cin >> S >> T; cout<<dijkstra()<<endl;     } }

细节有不懂欢迎提问,我随时可以解答,求点赞哈!

素描网