题目#

link

题解#

看到这个题，很像dp

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

dijkstra#

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

代码#

1
#include<bits/stdc++.h>
2

3
using namespace std;
4

5
const int N = 1100;
6
int dis[N];
7
bool vis[N];
8
int num[N], g[N][N], n;
9
int main()
10
{
11
  scanf("%d", &n);
12
  for(int i = 1;i <= n;i++)
13
    scanf("%d", &dis[i]);
14
  int a, b, c;
15
  for(int i = 1;i <= n;i++) num[i] = 1;
16
  while(scanf("%d%d%d", &a, &b, &c) != EOF)
17
  {
18
    a++, b++;
19
    g[a][b] = g[b][a] = c + 1;
20
  }
21
  dis[0] = 0x3f3f3f3f;
22
  while(1)
23
  {
24
    int x = 0;
25
    for(int i = 1;i <= n;i++)
26
    {
27
      if(!vis[i] && dis[i] < dis[x])
28
        x = i;
29
    }
30
    if(x == 0)
31
    {
32
      break;
33
    }
34
    vis[x] = 1;
35
    for(int y = 1;y <= n;y++)
36
    {
37
      if(g[x][y] == 0 || !vis[y]) continue;
38
      if(dis[g[x][y]] == dis[x] + dis[y])
39
      {
40
        num[g[x][y]] += num[x] * num[y];
41
      }
42
      else if(dis[g[x][y]] > dis[x] + dis[y])
43
      {
44
        dis[g[x][y]] = dis[x] + dis[y];
45
        num[g[x][y]] = num[x] * num[y];
46
      }
47
    }
48
  }
49
  cout << dis[1] << " " << num[1];
50
  return 0;
51
}