問題#
解法#
この問題を見たとき、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 の資料で説明されています。