题目链接：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;
}
| None | 360kB | 2482 | C++ | 2018-05-31 18:30:11 |