題目#
題解#
看到這個題，很像 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 課件有講