题目描述

一、建图：
想结婚，两条路，要么直接花钱购买聘礼（卖闺女，明码标价，童叟无欺？），要么用物品 + 钱去换。因此，可以将每件物品（包括女儿）抽象为图中的点，从一件物品换到另一件物品所花费的金钱抽象为图中边的权值；直接购买物品所花费的钱数，可以想象从一个特殊的虚拟点（即起点S），到其它点的权值。

这样，题目就变成了求从起点S到终点（女儿）的最短距离。

总结，通往女人内心的最短距离是金钱。

二、等级：
考虑每个等级区间（没办法，只有在一个圈子里的人才能进行交换）的最短距离，求其中的最小即可。

算法1

(朴素版Dijkstra) $O(n^3)$

题目中物品的个数N，$1 ≤ N ≤ 100$，可以使用朴素版Dijkstra算法，时间复杂度$O(n^2)$。
需要在在每个区间内，求一遍最短距离，因此时间复杂度为$O(n^3)$。

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 110;

//使用邻接矩阵g[][]存储图中边的权值
int g[N][N];
//level[i]表示i点的等级
int level[N];
//dis[i]表示虚拟起点S到点i的最短距离
int dis[N], st[N];
//m表示等级隔阂，n表示点的个数
int m, n; 

//dijkstra求虚拟起点S到（在等级范围[down, up]内的）所有点最短距离
int dijkstra(int down, int up)
{
    memset(dis, 0x3f, sizeof dis);
    memset(st, 0, sizeof st);

    dis[0] = 0; //起点S到自己的距离为0


    for(int i = 1; i <= n + 1; i++)
    {
        int t = -1;
        //求到起点0最短距离的点t
        for(int j = 0; j <= n; j++)
            //j点不在集合中，且j点的最短距离更小
            if(!st[j] && (t == -1 || dis[t] > dis[j]))
                t = j;

        st[t] = 1; //标记已使用

        //借助t点进行松弛
        for(int j = 1; j <= n; j++)
            //只考虑等级范围内的最短距离
            if(level[j] >= down && level[j] <= up)
                dis[j] = min(dis[j], dis[t] + g[t][j]);
    }
    return dis[1]; //返回到女儿的最短距离
}

int main()
{
    cin >> m >> n;

    memset(g, 0x3f, sizeof g);

    //点到自己的距离初始化为0
    for(int i = 1; i <= n; i++) g[i][i] = 0;

    //输入物品，建图
    for(int i = 1; i <= n; i++)
    {
        //价格，等级，可换物品的个数
        int p, l, x;
        cin >> p >> l >> x;
        //有重边，取最小
        g[0][i] = min(g[0][i], p), level[i] = l;
        while(x--)
        {
            //可换物品编号， 换后的权值
            int t, v;
            cin >> t >> v;
            //有重边，取最小，注意是用t物品换i物品
            g[t][i] = min(g[t][i], v); 
        }
    }

    int res = 0x3f3f3f3f;
    //枚举所有可以跟女儿进行交换的区间，求最短距离的最小值
    //女儿的等级为level[1]，那么最低可以更女儿进行交换的就是leve[1] - m
    //最高为女儿的等级level[1]
    for(int i = level[1] - m; i <= level[1]; i++)
        res = min(res, dijkstra(i, i + m));

    cout << res << endl;

    return 0;
}