正文
昂贵的聘礼 POJ - 1062
小程序：扫一扫查出行【扫一扫了解最新限行尾号】
复制小程序
题目链接：https://vjudge.net/problem/POJ-1062
如图，我们可以把交换的情况，抽象为一个有向图，
先抛去等级限制，那么就是一个最短路，从①出发，到达其他点的最短路中
最短的那个就是我们需要的答案了。
当然松弛条件变成了 dis[now] - pos[now].w + w(now->to) + pos[to].w < dis[to]，
这里，如果我们走了一条边，那么原来的最后加进去的物品的价格一定会发生改变，那么我们把原来的物品价格减去，
改成交换后的价格，然后要加上我们买to的那个物品的价格，然后与dis[to]比较。
等级限制，就是说你在交换物品的路上，你交换物品的所有商人集合记为P，某人商人记为px，
∀pi , pj∈P， abs(pi.level - pj.level) <= L.那么我们需要记录你一路上商人的等级，当然，我们只需要考虑极端情况就好了，
记录一个最低等级，一个最高等级，如果这两个满足，那么其他商人都会满足。代码会有解释。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <stack>
#include <string>
#include <map>
#include <cmath>
#include <iomanip>
using namespace std; typedef long long LL;
#define inf 1e9
#define rep(i,j,k) for(int i = (j); i <= (k); i++)
#define rep__(i,j,k) for(int i = (j); i < (k); i++)
#define per(i,j,k) for(int i = (j); i >= (k); i--)
#define per__(i,j,k) for(int i = (j); i > (k); i--) const int N = ;
int head[N];
bool vis[N];
int dis[N];
int cnt;
int L,n; struct Pos{
int w;
int level;
}pos[N]; struct Edge{
int to;
int w;
int next;
}e[(int)1e7]; struct node{
int loc;//当前位置
int level_max;//之前的最高等级
int level_min;//最浅的最低等级
int dis;//距离
bool friend operator< (const node& a,const node& b){
return a.dis > b.dis;
}
}; priority_queue<node> que; void add(int u,int v,int w){
e[cnt].to = v;
e[cnt].w = w;
e[cnt].next = head[u];
head[u] = cnt++;
} //我们要交换的商人 与之前的最高和最低等级是否满足等级限制
inline bool check_loc(node& now,int to){
return abs(now.level_max - pos[to].level) <= L && abs(now.level_min - pos[to].level) <= L;
} void dijkstra(){ rep(i,,n) dis[i] = inf;
dis[] = pos[].w;
que.push(node{, pos[].level, pos[].level, dis[]}); node now;
int to,w;
while(!que.empty()){ now = que.top();
que.pop();
if(vis[now.loc]) continue;
vis[now.loc] = true; for(int o = head[now.loc]; ~o; o = e[o].next){
to = e[o].to;
w = e[o].w; if(dis[now.loc] - pos[now.loc].w + w + pos[to].w < dis[to] && check_loc(now,to)){
dis[to] = dis[now.loc] - pos[now.loc].w + w + pos[to].w;
//更新遇到的最高等级和最低等级
que.push(node{to, min(now.level_min, pos[to].level), max(now.level_max, pos[to].level),
dis[to]});
}
}
} int ans = inf;
rep(i,,n) ans = min(ans,dis[i]);
cout << ans << endl;
} int main(){ scanf("%d%d",&L,&n); rep(i,,n) head[i] = -;
cnt = ;
int tot,v,w;
rep(u,,n){
scanf("%d%d%d",&pos[u].w,&pos[u].level,&tot);
rep(j,,tot){
scanf("%d%d",&v,&w);
add(u,v,w);
}
} dijkstra(); getchar(); getchar();
return ;
}
