[Acwing] 最短路计数 最短路+DP

前言

讲理论讲了好久,差点干困了QAQ 传送门 :

思路

对于本题来说,无权图即边权都为1,不存在边权为0

使得答案 a n s = I N F ans = INF ans=INF的情况

因此对于 D I J DIJ DIJ算法中的松弛操作

d i s t [ j ] = d i s t [ t ] + w [ i ] dist[j] = dist[t]+w[i] dist[j]=dist[t]+w[i] 我们可以对每一个 j j j 都设置 他的 前驱节点 t t t

从而使得获得一个 最短路树

树本身就满足拓扑

所以我们可以直接采用之前 d p dp dp 的方法 记录所有的方案数

CODE

// Problem: 最短路计数
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/1136/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include 
using namespace std;
#define ll long long
#define endl '\n'
#define pb push_back
#define x first
#define y second
typedef pair PII;

const int N = 1e5+10,mod = 1e5+3;
vector g[N];
int dist[N],cnt[N];
int st[N];
int n,m;

void dij()
{
	memset(dist,0x3f,sizeof dist);
	
	dist[1] = 0;
	cnt[1] = 1;
	
	priority_queue heap;
	heap.push({0,1});
	
	while(!heap.empty())
	{
		auto t = heap.top();
		heap.pop();
		
		int ver = t.y ,distance  = t.x;
		
		if(st[ver])
		continue;
		st[ver] = true;
		
		for(auto x : g[ver])
		{
			if(dist[x] > distance+1)
			{
				dist[x] = distance  +1;
				cnt[x] = cnt[ver];
				heap.push({dist[x],x});
			}
			else
			if(dist[x] == distance +1 )
			cnt[x] = (cnt[x]+cnt[ver])%mod;
			
		}
		
	}
	
}
void solve()
{
   cin>>n>>m;
   while(m -- )
   {
   		int a,b;cin>>a>>b;
   		g[a].pb(b);
   		g[b].pb(a);
   }
   
   dij();
   for(int i=1;i