POJ(1062)(昂贵的聘礼)

链接：https://vjudge.net/problem/POJ-1062#author=0
思路：题目描述有点别扭，第一次被误导了以为是不能比之前交易低的交易，没想到只是背景后来改变规则了，要求的是阶级不超过m的可以交易（所有交易中的最大和最小），那么就肯定不能单笔交易比较阶级了，我们考虑枚举一下阶级的范围，因为必须要包含酋长的阶级，所以区间在[酋长阶级-m,酋长阶级+m]中长度为m的连续子区间，那么跑最短路时判断一下当前边的两边是否在区间内，如果在内则更新，不在内不更新，最后取所有跑的最短路中的最小值即可。
代码：

#include<cstdio>
#include<queue>
#include<functional>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;

typedef pair<int,int> P;
int n,rr;
int sx,ex;

struct edge{
    int from,to,dist;
    edge(int f,int t,int d){
        from = f;
        to = t;
        dist = d;
    }
};

const int maxn = 110;

struct Dij{
    int d[maxn];
    int r[maxn];
    vector<int> G[maxn];
    vector<edge> edges;
    int n,m;

    void init(int n){
        this->n = n;
        for(int i=0;i<=n;i++)G[i].clear();
        edges.clear();
        memset(r,0,sizeof(r));
    }

    void addedge(int from,int to,int dist){
        edges.push_back(edge(from,to,dist));
        m = edges.size();
        G[from].push_back(m-1);
    }

    void dij(int w){
        for(int i=0;i<=n;i++)d[i] = 1e9;
        d[w] = 0;
        priority_queue<P,vector<P>,greater<P> > q;
        q.push(P(0,w));
        while(!q.empty()){
            P p = q.top();
            q.pop();
            int u = p.second;
            if(r[u]!=-1&&(d[u]<p.first||r[u]>ex||r[u]<sx))continue;//判断边起点是否合法，注意起点0要单独特判-1
            for(int i=0;i<G[u].size();i++){
                edge e = edges[G[u][i]];
                if(d[e.to]>d[u] + e.dist&&r[e.to]<=ex&&r[e.to]>=sx){//判断边终点是否在枚举的区间内
                    d[e.to] = d[u] + e.dist;
                    q.push(P(d[e.to],e.to));
                }
            }
        }
    }
}solver;

int k;
int cost;
vector<P> mat[maxn];

int main(){
    while(~scanf("%d%d",&rr,&n)){
    solver.init(n);
    solver.r[0] = -1;
    for(int i=0;i<=n;i++)mat[i].clear();
    for(int i=1;i<=n;i++){
        scanf("%d%d%d",&cost,&solver.r[i],&k);
        solver.addedge(0,i,cost);
        int nn;
        for(int j=0;j<k;j++){
            scanf("%d%d",&nn,&cost);
            mat[i].push_back(P(nn,cost));
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<mat[i].size();j++){
            pair<int,int> p = mat[i][j];
                solver.addedge(p.first,i,p.second);
        }
    }
    int res = 1e9;
    for(sx=solver.r[1]-rr;sx<=solver.r[1];sx++){//枚举区间跑最短路
        ex = sx + rr;
        solver.dij(0);
        res = min(res,solver.d[1]);;//更新最小值
    }
    printf("%d\n",res);
    }
    return 0;
}