9.2 图论专项四模拟赛小记

Moyyer_suiy / 2023-09-04 / 原文

A.最短路，原题洛谷指路：P1144 最短路计数

看评测一开始 0pts，死于无向边看成单向边。后来在洛谷提交的时候调了好久好久，死于数组开小。

其他没什么，就是一个 dijkstra 的板子。转移路径的时候，若这条路比当前的路长度小，那这条路的答案就更新为转移过来新路的答案；若这条路和当前路长度一样，那将答案加上新路。

#include<bits/stdc++.h>
using namespace std;
const int N = 2e6 + 10;
const int mod = 1e5 + 3;
int n, m;
int vis[N];
priority_queue< pair<int, int> > q;
int idx, e[N], w[N], nxt[N], head[N];
struct node{int d, tot;}ans[N];
void add(int x, int y, int z)
{
	e[++ idx] = y;
	w[idx] = z;
	nxt[idx] = head[x];
	head[x] = idx;
}
void dij()
{
	ans[1].d = 0;
	ans[1].tot = 1;
	q.push(make_pair(0, 1));
	while(q.size())
	{
		int x = q.top().second;
		q.pop();
		if(vis[x]) continue;
		vis[x] = 1;
		for(int i = head[x]; i; i = nxt[i])
		{
			if(ans[e[i]].d == ans[x].d + 1) ans[e[i]].tot = (ans[e[i]].tot + ans[x].tot) % mod;
			else if(ans[e[i]].d > ans[x].d + 1)
			{
				ans[e[i]].d = ans[x].d + 1;
				ans[e[i]].tot = ans[x].tot % mod;
				q.push(make_pair(-ans[e[i]].d, e[i]));
			}
		}
	}
}
int main()
{
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i ++ ) ans[i].d = 1e9;
	while(m -- )
	{
		int x, y;
		scanf("%d%d", &x, &y);
		add(y, x, 1);
		add(x, y, 1);
	}
	dij();
	for(int i = 1; i <= n; i ++ ) printf("%d\n", ans[i].tot % mod);
	return 0;
}