最短路径，Dijkstra算法。
根据题意将每种物品看成每个顶点，优惠价格看成边，便构成一有向图，然后可以用Dijkstra求解。因为有等级限制，求一次Dijkstra是不行的。思想是枚举0~L的每一种限制i，除去不在区间[rand[1]-i,rand[i]+m-i](rand[1]为酋长的等级)的顶点，然后Dijkstra，取其中最小的。例如假设酋长等级为5，等级限制为2，那么需要枚举等级从3~5,4~6,5~7。从满足改等级范围的结点组成的子图中用Dijkstra来算出最短路径，最后求出最小值。构图时要注意的是，酉长的承诺不是最初的源点，它是一个目标点，也就是说点到点的指向方向是由无替代品的点逐渐指向到 酉长的承诺（1点），题意说明的是一个回溯的过程，因此可以定义一个最初的源点（0点），它到其他各点的权值就是每个物品的原价，而点A到点B的权值就是 物品B在有第A号替代品情况下的优惠价。还有知道了memset是以字节为单位的，所以初始化为最大值的时候，有时候不能用memset。
#includeusing namespace std;#define LEN 110const int INF (1<<30);int N;int M;int graph[LEN][LEN];int dist[LEN];int value[LEN];int level[LEN];bool visit[LEN];void init() { cin >> M >> N; for(int i = 0; i <= N; i++) for(int j = 0; j <= N; j++) if(i == j) graph[i][j] = 0; else graph[i][j] = INF; for(int i = 1;i <= N; i++) { int x; cin >> value[i] >> level[i] >> x; for(int j = 1; j <= x; j++) { int t, u; cin >> t >> u; graph[t][i] = u; } } } int dijkastra(){ for (int i = 1; i <= N; i++) { dist[i] = value[i]; } for (int i = 1; i <= N; i++) { int n = 0; int min = INF; for (int j = 1; j <= N; j++) { if (!visit[j] && dist[j] < min) { n = j; min = dist[j]; } } if (n == 0) break; visit[n] = true; for (int j = 1; j <= N; j++) { if (!visit[j] && dist[n] + graph[n][j] < dist[j]) { dist[j] = dist[n] + graph[n][j]; } } } return dist[1];}int main(){ init(); int result = INF; for (int i = 0; i <= M; i++) { int maxLevel = level[1] + i; for (int j = 1; j <= N; j++) { if (level[j] > maxLevel || maxLevel - level[j] > M) { visit[j] = true; } else { visit[j] = false; } } int min = dijkastra(); if (min < result) result = min; } cout << result << endl; return 0;}