POJ 1062

• 题意：

  1. 替换就相当于一条指向另一个点的有向边,权值是价值,但是每个点都有等级作为限制条件,
  2. 限制条件还必须在一个范围,例如:
     level[1] = 3 m=1,节点等级限制范围:[2,3]、[3,4],
     level[1] = 3 m=2, 范围：[1,3]、[2,4],[3,5]
  3. 每次最短路在将不再范围的点排除,然后取每个范围中最短的点.

  #include <iostream>
  #include <queue>
  #include <string.h>
  
  using namespace std;
  const int maxn = 105;
  const int inf = 0x3f3f3f3f;
  
  int e[maxn][maxn];
  int dist[maxn];
  int level[maxn];
  bool vis[maxn];
  int value[maxn];
  int n,radium;
  
  int dij() {
  	priority_queue<pair<int,int> > que;
  	memset(dist,0x3f,sizeof dist);
  	dist[1] = 0;
  	que.push( make_pair(-dist[1],1) );
  	while (!que.empty()) {
  		int cur = que.top().second; que.pop();
  		if (vis[cur]) continue;
  		vis[cur] = 1;
  		for (int i=1; i<=n; i++) {
  			if (!vis[i] && dist[i] > dist[cur] + e[cur][i]) {
  				dist[i] = dist[cur] + e[cur][i];
  				que.push( make_pair(-dist[i],i) );
  			}
  		}
  	}
  	int MIN = inf;
  	for (int i=1; i<=n; i++) 
  		MIN = min(MIN,dist[i]+value[i]);
  	return MIN;
  }
  
  int main() {
  //	freopen("a.txt","r",stdin);
  	cin >> radium >> n;
  	memset(e,0x3f,sizeof e);
  	int k;
  	for (int i=1; i<=n; i++) {
  		cin >> value[i] >> level[i] >> k;
  		for (int j=1; j<=k; j++) {
  			int to,div;
  			cin >> to >> div;
  			e[i][to] = div;
  		}
  	}
  	int ans = inf;
  	for (int i=0; i<=radium; i++) { // 枚举一路的等级区间范围
  		memset(vis,0,sizeof vis);
  		for (int j=1; j<=n; j++) 
  			// 把超出等级范围的点这一轮排除掉
  			if (level[1] - radium + i > level[j] || level[j] > level[1] + i)
  				vis[j] = 1;
  		ans = min(ans,dij());
  	}
  	cout << ans;
  	return 0;
  }