AcWing 903. 昂贵的聘礼

思路

建立虚拟源点

每一个物品都有一个初始价格, 初始价格我们定义为虚拟源点到当前点的权值.

每次从虚拟源点出发遍历图, 寻找1点的最短路

本题有等级限制, 等级限制其实就是决定了 图遍历的范围, 不同范围得出的结果不同,所以每一个限制我们都要遍历一遍

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 110;

int level[N];
int st[N];
int dist[N];
int w[N][N];
int n, l;

int dijistra(int down, int up)
{
  	// 初始化
    memset(dist, 0x3f, sizeof dist);
    memset(st, 0, sizeof st);
  
  	// 虚拟源点距离为0
    dist[0] = 0;
    
    for(int i = 0; i <= n; i++)
    {
        
        int t = -1;
        
        for(int j = 0; j <= n; j++)
        {
            if(!st[j] && (t == -1 || dist[j] < dist[t]))
                t = j;
        }

                
        for(int j = 1; j <= n; j++)
        {
          	// 等级符合的点
            if(level[j] >= down && level[j] <= up) 
                dist[j] = min(dist[j], dist[t] + w[t][j]);
        }
        st[t] = 1;
    }
    
    return dist[1];
}

int main()
{
  	// 初始化邻接矩阵
    memset(w, 0x3f, sizeof w);
    for(int i = 0 ; i <= N; i++) w[i][i] = 0;
    
    cin >> l >> n;
    for(int i = 1 ; i <= n; i++)
    {
        int x, m;
        cin >> x >> level[i] >> m;
      	// 建立虚拟源点的距离
        w[0][i] = min(w[0][i], x);
        while(m--)
        {
            int a, b;
            cin >> a >> b;
            w[a][i] = min(w[a][i], b);
        }
    }
    
  	// 不同等级区间遍历一遍寻找最小值
    int ans = 0x3f3f3f3f;
    for(int i = level[1] - l; i <= level[1]; i++) ans = min(ans,dijistra(i, i + l));
    
    cout << ans;
    return 0;
}