POJ-1062 昂贵的聘礼有限制的最短路

题目链接：https://cn.vjudge.net/problem/POJ-1062

题意

虽然是中文题，还是简单复述一下吧

我们想要酋长的女儿作为老婆。作为交换，酋长想要点钱。

酋长提出可以用其他人的东西来降低价格，然而其他人也想通过别人的东西来降低他们的价格。

由于每个人等级不一样，所以在每一条“交易链”中，不能出现地位差值大于M的情况。

求老婆的最小价值

思路

直接转化为最短路问题，难点在于如何处理地位差和物品价格（老婆价值=边权和+物品价格）的问题

受到Dijkstra的启发，我们可以设两个数组minLevel, maxLevel作为某交易链中的最小地位和最大地位

这样在松驰操作前，可以直接判断该节点可否更新（地位是否可行）
物品价格更好处理，处理完边权后，在dist上直接加价格即可

代码

#include <queue>

#include <vector>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int maxn=110, maxm=maxn*maxn, INF=0x3f3f3f3f;

typedef pair<long long, int> Node;

struct Edge{

    int to, next;

    long long cost;

    Edge(int to=0, int next=9, long long cost=0):

        to(to), next(next), cost(cost) {}

}edges[maxm+5];

struct Cmp{

    bool operator () (const Node &a, const Node &b){

        return a.first>b.first;

    }

};

struct Point{

    long long price;

    int level;

    Point(long long price=0, int level=0):

        price(price), level(level) {}

}points[maxn+5];

int head[maxn], esize, minlv[maxn+5], maxlv[maxn+5], n, m;

long long dist[maxn+5];

void addEdge(int from, int to, long long cost){

    edges[esize]=Edge(to, head[from], cost);

    head[from]=esize++;

}

void init(void){

    memset(head, -1, sizeof(head));

    esize=0;

}

inline bool outer(const int &to, const int &from){

    if (abs(minlv[from]-points[to].level)<=m && abs(maxlv[from]-points[to].level)<=m)

        return false;

    return true;

}

long long Dij(void){

    priority_queue<Node, vector<Node>, Cmp> que;

    memset(dist, INF, sizeof(dist)); dist[1]=0;

    memset(maxlv, 0, sizeof(maxlv));

    memset(minlv, INF, sizeof(minlv));

    maxlv[1]=minlv[1]=points[1].level;

    que.push(Node(dist[1], 1));

    while (que.size()){

        Node x=que.top(); que.pop();

        if (x.first!=dist[x.second]) continue;

        int &from=x.second;

        for (int i=head[from]; i!=-1; i=edges[i].next){

            Edge &e=edges[i];

            int &to=e.to, &level=points[to].level;

            long long &dis=e.cost;

            if (outer(to, from) || dist[to]<=dist[from]+dis) continue;

            dist[to]=dist[from]+dis;

            maxlv[to]=max(maxlv[from], level);

            minlv[to]=min(minlv[from], level);

            que.push(Node(dist[to], to));

        }

    }

    long long ans=INF;

    for (int i=1; i<=n; i++)

        ans=min(dist[i]+points[i].price, ans);

    return ans;

}

int main(void){

    int price, level, x, to;

    long long cost;

    while (scanf("%d%d", &m, &n)==2 && n){

        init();

        for (int from=1; from<=n; from++){

            scanf("%lld%d%d", &points[from].price, &points[from].level, &x);

            for (int i=0; i<x; i++){

                scanf("%d%lld", &to, &cost);

                addEdge(from, to, cost);

            }

        }

        printf("%lld\n", Dij());

    }

    return 0;

}

Time	Memory	Length	Lang	Submitted
None	360kB	2482	C++	2018-05-31 18:30:11

巴特西

POJ-1062 昂贵的聘礼有限制的最短路

题意

思路

代码

最新文章

热门文章

巴特西

POJ-1062 昂贵的聘礼 有限制的最短路

题意

思路

代码

最新文章

热门文章

POJ-1062 昂贵的聘礼有限制的最短路