AcWing 383. 观光(上课摸鱼(×)开摆(√))

题目

题意: 给定n个点，m条有向边。给定起点S和终点T。求最短路的方案数 + 仅比最短路长度大1的路径的方案数.

思路: Dij + dp.涉及到dp我就不会了。 最短路方案数易求,比最短路长度大1的路径方案数是关键。Dij预处理距离数组dist[] 考虑dp: f[u][k]: 表示到u点长度为dist[u] + k的方案数 答案为f[T][0] + f[T][1] 转移: f[j][k] = f[j][k] + f[u][k], if(dist[j] == dist[u] + w[i]). 到达u长度为dist[u] + k的方案数,会被到j长度为dist[j] + k所继承，因为j恰好可以通过u到达。 f[j][1] = f[j][1] + f[u][0], if(dist[j] + 1 == dist[u] + w[i]) 到达j长度为dist[j] + 1的方案数，可以继承到达u长度为dist[u]的方案数。

// Problem: 观光
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/385/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define OldTomato ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define fir(i,a,b) for(int i=a;i dist[u] + w[i])
			{
				dist[j] = dist[u] + w[i];
				q.push({dist[j],j});
				cnt[j] = cnt[u];
			}
			else if(dist[j] == dist[u] + w[i])
			{
				cnt[j] += cnt[u];
			}
		}
	}
}
struct s2 //按照dist数组排序
{
	int id;
	int dis;
	bool operator