题意简述

你想娶酋长的女儿，但酋长要求你给一定数额金钱的聘礼。除了金钱外，酋长也允许你用部落里其他人的某物品加上一点钱作为聘礼。而其他人的物品也可以通过指定的另外一些人的某物品加上一些金钱获得。部落里的每个人有一个等级。你的整个交易过程涉及的人的等级只能在一个限定的差值内。问你最少需要多少金钱才能娶到酋长女儿。假定每个人只有一个物品。

例：

最高最低等级差不超过1，共4个物品
酋长的女儿      等级3     要求现金10000元     或甲的物品+8000元     或乙的物品+5000元
甲的物品        等级2     要求现金1000元      或丙的物品+200元
乙的物品        等级2     要求现金3000元      或丙的物品+200元
丙的物品        等级2     要求现金50元

在这个例子中，最少花费方案是：买丙的东西（50）换乙的东西（+200）换酋长女儿（+5000）一共5250元。

算法分析

容易想到这题可以将它转换为一张有向图。边权代表由A到B所需要附加的金钱。由于每个人只有一个物体，所以节点既可以代表人也可以代表人手中的物品。

上面的例子可以转换为如下一张图：

图中蓝色线路即最低花销路线。

我们可以很容易的看出，这题是单源最短路。可以用Dijkstra解决。

唯一遗留的问题就是等级限制。

因为线路中最高最低等级差不能超过给定值m，所以我们枚举等级区间，设酋长等级为l，则从[l-m,l]枚举到[l,l+m]。对于每一个区间，我们进行筛选，对不满足的点在Dijkstra使用的松弛标记数组visit[]中标记为已访问。则可以避免它参与松弛。（注意每次枚举前对它初始化。）筛选后对区间进行Dijkstra。并将结果比较替换当前最优解。直到枚举结束。

Problem Status: AC。时间0ms，内存200k

程序样例

#include<stdio.h>
#define MaxI 99999999

int min(int a, int b) {
  return a < b ? a : b;
}

int dijkstra(int n, int map[][101], int vis[]) {
  int dis[101] = {
    0
  }, min, t, i;
  for (i = 1; i <= n; i++)
    dis[i] = map[0][i];
  while (1) {
    min = MaxI;
    for (i = 1; i <= n; i++)
      if ((vis[i] == 0) && (dis[i] < min)) {
        min = dis[i];
        t = i;
      }
    if (min == MaxI) break;
    vis[t] = 1;
    for (i = 1; i <= n; i++)
      if ((!vis[i]) && (map[t][i] != MaxI) && (dis[i] > dis[t] + map[t][i]))
        dis[i] = dis[t] + map[t][i];
  }
  return dis[1];
}

int main() {
  int m, n, l[101], x, i, j, t, v, map[101][101], vis[101], ans = MaxI;
  scanf("%d%d", & m, & n);
  for (i = 0; i <= n; i++)
    for (j = 0; j <= n; j++)
      map[i][j] = MaxI;
  for (i = 1; i <= n; i++) {
    scanf("%d%d%d", & map[0][i], & l[i], & x);
    for (j = 0; j < x; j++) {
      scanf("%d%d", & t, & v);
      map[t][i] = v;
    }
  }
  l[0] = l[1];
  for (i = l[1] - m; i <= l[1]; i++) {
    vis[0] = 1;
    for (j = 1; j <= n; j++)
      if ((l[j] >= i) && (l[j] <= (i + m))) vis[j] = 0;
      else vis[j] = 1;
    ans = min(ans, dijkstra(n, map, vis));
  }
  printf("%d\n", ans);
  return 0;
}