题目

link

题解

看到这个题，很像dp

但是它可能有环，所以不能dp。又因为都是正数，可以考虑用dijkstra的形式来做“dp”

dijkstra

需要注意的是，做dijkstra的时候需要注意一条边x->y只有在x和y都确定了最小值的前提下才能够更新其他点，否则出现有些点生下来就是最小值的时候就会被重复计算方案数目。

代码

#include<bits/stdc++.h>

using namespace std;

const int N = 1100;
int dis[N];
bool vis[N];
int num[N], g[N][N], n;
int main()
{
	scanf("%d", &n);
	for(int i = 1;i <= n;i++)
		scanf("%d", &dis[i]);
	int a, b, c;
	for(int i = 1;i <= n;i++) num[i] = 1;
	while(scanf("%d%d%d", &a, &b, &c) != EOF)
	{
		a++, b++;
		g[a][b] = g[b][a] = c + 1;
	}
	dis[0] = 0x3f3f3f3f;
	while(1)
	{
		int x = 0;
		for(int i = 1;i <= n;i++)
		{
			if(!vis[i] && dis[i] < dis[x])
				x = i;
		}
		if(x == 0)
		{
			break;
		}
		vis[x] = 1;
		for(int y = 1;y <= n;y++)
		{
			if(g[x][y] == 0 || !vis[y]) continue;
			if(dis[g[x][y]] == dis[x] + dis[y])
			{
				num[g[x][y]] += num[x] * num[y];
			}
			else if(dis[g[x][y]] > dis[x] + dis[y])
			{
				dis[g[x][y]] = dis[x] + dis[y];
				num[g[x][y]] = num[x] * num[y];
			}
		}
	}
	cout << dis[1] << " " << num[1];
	return 0;
}

spfa

sdsc 2022 day6课件有讲