POJ1062.md

建图跑最短路，限制等级，那就枚举可以进行交易的人的等级区间，每次最短路的之后只能走那些等级在当前范围内的点，要把酋长即1号点包含进去 所有点向一个超级源点建边，边权为直接交易的价格，其他的就正常建边，取最大值即可

#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>
#include<functional>
#include<utility>
#include<iostream>
using namespace std;
const int MAXN = 222;
typedef long long LL;
const LL INF = 0x3f3f3f3f3f3f3f3f;
int m,n,status[MAXN];
LL dist[MAXN];
vector<pair<int,int> > G[MAXN];
void Dijkstra(int L, int R){
    for(int i = 2; i <= n; i++) dist[i] = INF;
    priority_queue<pair<LL,int>,vector<pair<LL,int> >, greater<pair<LL,int> > > que;
    que.push(make_pair(dist[1],1));
    while(!que.empty()){
        pair<LL,int> p = que.top();
        que.pop();
        int u = p.second;
        LL cost = p.first;
        if(dist[u]!=cost) continue;
        for(int i = 0; i < (int)G[u].size(); i++){
            pair<int,int> &e = G[u][i];
            int v = e.first, cst = e.second;
            if(v==n+1){
                dist[v] = min(dist[v],dist[u]+cst);
                continue;
            }
            if(L>status[v] || R<status[v]) continue;
            if(dist[v]>dist[u]+cst){
                dist[v] = dist[u] + cst;
                que.push(make_pair(dist[v],v));
            }
        }
    }
}
int main(){
    while(scanf("%d %d",&m,&n)!=EOF){
        for(int i = 1; i <= n; i++) G[i].clear();
        for(int i = 1; i <= n; i++){
            int v,k;
            scanf("%d %d %d",&v,&status[i],&k);
            G[i].push_back(make_pair(n+1,v));
            for(int j = 1; j <= k; j++){
                int to, c;
                scanf("%d %d",&to,&c);
                G[i].push_back(make_pair(to,c));
            }
        }
        memset(dist,0x3f,sizeof(dist)); dist[1] = 0;
        for(int i = status[1]-m; i <= status[1]; i++) Dijkstra(i,i+m);
        printf("%lld\n",dist[n+1]);
    }
    return 0;
}