题目链接： 中文题目，就不说题意了.
分析： 很好的一道题。两个关键：一是建图，而是处理等级限制的问题。 建图的话，结点为每件物品，把探险者也看成一个入度为零的节点，是n + 1结点之一，我把他的标号设为0，探险者到其他物品的直接连线的权值为物品的原始价格，其他 i -> j的边的权值为探险者获得i后换j的优惠价格。 题目又要求最短路中的所有点的等级在一个区间内[a,b]，如果能够很好的给出这个区间的话，只要
对图中的点进行筛选即可了。 从题意中我们知道，最后所有的最短路都会汇集在1号点，也就是说1号点是所有最短路都存在的点，好了，这个条件很重要，这样我们就可以依照1号点来给定区间了，比如1号点等级为lev，那么也就是说在所有最短路的这些点都必须满足在[lev-M,lev+M]这个区间里面。但是如果在这个区间内出现的两个点的他们之间的等级差超过了M值（这是存在的），显然，不符合题意了，所以这个区间还要继续缩小。其实只要稍微动动脑子，就可以找出这样的区间[lev-M,lev],[lev-M+1,lev+1],... ...,[lev,lev+M]，首先这些区间都满足大区间的条件，而且如果将这些区间的某个作为筛选条件的话，在这个区间内的任意两个点的等级都不会超过M值，这是本题的精华所在。 好了，讲完了，只需枚举区间，然后筛选点，求最短路就行了。
#include #include #include #include #include #include #include #include #include #include #include #include #define MID(x,y) ((x+y)>>1)#define mem(a,b) memset(a,b,sizeof(a))using namespace std;typedef long long LL;const int sup = 0x7fffffff;const int inf = -0x7fffffff;const int MAXE = 5000;const int MAXV = 103;struct Substitutes{ int id, price;};struct condition{ int P, L, X; vector sub;}con[MAXV];struct node{ int u, v, w; int next;}edge[MAXE];int cnt, head[MAXV];void init(){ mem(head, -1); mem(edge, -1); cnt = 0;}void add(int u, int v, int w){ edge[cnt].u = u; edge[cnt].v = v; edge[cnt].w = w; edge[cnt].next = head[u]; head[u] = cnt ++;}int n, m;int dis[MAXV];int vis[MAXV];priority_queue , vector >, greater > > PQ;void Dijkstra(int s){ int ans = sup; for (int k = 0; k <= m; k ++){ for (int i = 1; i <= n; i ++){ if (con[i].L - con[1].L <= k && con[1].L - con[i].L <= (m-k)) vis[i] = 0; else vis[i] = 1; } vis[0] = 0; for (int i = 0; i <= n; i ++) dis[i] = sup; dis[s] = 0; while(!PQ.empty()) PQ.pop(); PQ.push(make_pair(0, s)); while(!PQ.empty()){ int u = PQ.top().second; PQ.pop(); if (!vis[u]){ vis[u] = 1; for (int i = head[u]; i != -1 ; i = edge[i].next){ int v = edge[i].v; if (dis[v] > dis[u] + edge[i].w){ dis[v] = dis[u] + edge[i].w; PQ.push(make_pair(dis[v], v)); } } } } ans = min(ans, dis[1]); } printf("%d\n", ans);}int main(){ init(); scanf("%d %d", &m, &n); for (int i = 1; i <= n; i ++){ scanf("%d %d %d", &con[i].P, &con[i].L, &con[i].X); for (int j = 0; j < con[i].X; j ++){ Substitutes tmp; scanf("%d %d", &tmp.id, &tmp.price); con[i].sub.push_back(tmp); } } for (int i = 1; i <= n; i ++){ add(0, i, con[i].P); for (int j = 0; j < con[i].X; j ++){ Substitutes p = con[i].sub[j]; if (abs(con[i].L - con[p.id].L) <= m){ add(p.id, i, p.price); } } } Dijkstra(0); return 0;}