Problem#
Solution#
Seeing this problem, it looks very much like dynamic programming (dp).
However, it may have cycles, so we cannot use dp. Since all values are positive, we can consider using Dijkstra's algorithm to perform "dp".
Dijkstra#
It is important to note that when performing Dijkstra's algorithm, an edge x->y can only update other points if both x and y have determined their minimum values. Otherwise, if some points are initialized as minimum values, the number of ways to compute them will be counted multiple times.
Code#
#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#
The sdsc 2022 day6 lecture notes have discussed this.