POJ 1062 昂贵的聘礼(The shortest path)

Description

男方去女方家提亲，女方提出要 P 彩礼，男方觉得有点多，于是女方提出可以拿 物品T 来，那样彩礼只要 V。物品T在第 i 个人那里， 男方去求取，遇到了同样的困难：要钱太多但倘若拿来某物品，可以给他优惠。

女方这边有等级差别，你所交易的人中，任意两人等级不可大于M。

Input

M(等级差别限制) N(可交易人 1 ~ N 1是女方家里人，是最终要交易的对象)

接下来N个描述

P(该交易人所有物品的价值) ——每个交易人只有一个物品

L(该交易人等级)

X(优惠方案数)

紧跟X行， 每行 T(交易人编号) V(该交易人物品价格)

花最少的钱取到1号手里的物品：那个她

Analyze

先撇开等级限制，可以Dijkstra求出点1到其他所有点的最短路dis[i]，那么dis[i]+val[i] 就是一直换到物品i的最少花费，由于最终换到谁才满足花费最少不确定，所以遍历一遍取最小值即可。

再考虑等极限制，由于必定与1交易，所以交易人等级区间为[val[1]-M,val[1]+M]，但有可能交易时出错，比如跟val[1]-M和val[1]+M交易，那么他俩等级差都2M了。所以可行区间应为[val[1]-M, val[1]]、[val[1]-M+1, val[1]+1]……遍历枚举区间即可

Attention

图是有向图（边是单向边）

Code

#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;

int m, n;
vector<int> vec;
bool vis[105];
int val[105], lev[105], e[105][105], dis[105];

int Dijkstra()
{
    memset(dis, INF, sizeof(dis));
    memset(vis, 0, sizeof(vis));

    dis[1] = 0;
    int mmin = INF, pos = 0, sz = vec.size();
    for(int i = 0; i < sz; ++i)
    {
        mmin = INF, pos = 0;
        for(int j = 0; j < sz; ++j)
        {
            int to = vec[j];
            if(!vis[to] && dis[to] < mmin)
            {
                mmin = dis[to];
                pos = to;
            }
        }
        vis[pos] = 1;
        for(int j = 0; j < sz; ++j)
        {
            int to = vec[j];
            if(vis[to])
                continue;
            if(dis[to] > dis[pos] + e[pos][to])
                dis[to] = dis[pos] + e[pos][to];
        }
    }

    int res = INF;
    for(int i = 0; i < sz; ++i)
    {
        int to = vec[i];
        dis[to] += val[to];
        res = min(res, dis[to]);
    }

    return res;
}

int main()
{
    scanf("%d %d", &m, &n);

    for(int i = 1; i <= n; ++i)
        for(int j = i; j <= n; ++j)
            e[i][j] = e[j][i] = INF;

    int P, L, X, T, V;
    for(int i = 1; i <= n; ++i)
    {
        scanf("%d %d %d", &P, &L, &X);
        val[i] = P, lev[i] = L;
        for(int j = 1; j <= X; ++j)
        {
            scanf("%d %d", &T, &V);
            e[i][T] = V;///The graph is directed.
        }
    }

    int ans = INF;
    for(int down = lev[1] - m; down <= lev[1]; ++down)
    {
        vec.clear();
        for(int j = 1; j <= n; ++j)
            if(lev[j] >= down && lev[j] <= down + m)
                vec.push_back(j);

        ans = min(ans, Dijkstra());
    }
    cout << ans << '\n';
    return 0;
}