Input
Output
Sample Input
1 4 10000 3 2 2 8000 3 5000 1000 2 1 4 200 3000 2 1 4 200 50 2 0
Sample Output
5250
解题思路：
最短路径——Dijkstra算法
此题的关键在于等级限制的处理，采用枚举，即假设酋长等级为5，等级限制为2，那么需要枚举等级从3~5,4~6,5~7
从满足改等级范围的结点组成的子图中用Dijkstra来算出最短路径，最后求出最小值。
也就是枚举出这样的区间[lev-M,lev],[lev-M+1,lev+1],... ...,[lev,lev+M] lev 即rank[1]
1 #include <stdio.h> 2 #include <algorithm> 3 #include <iostream> 4 #include <stdlib.h> 5 #include <math.h> 6 #include <stack> 7 8 #define INF 0x3f3f3f3f 9 using namespace std; 10 int map[110][110], n; 11 int ranks[110], value[110], dist[110]; 12 int mark[110], within[110]; 13 14 int Dijkstra () 15 { 16 int i, j, k, min; 17 memset(mark,0,sizeof(mark)); 18 for ( i = 1; i <= n; i++ ) 19 dist[i] = map[1][i]; 20 dist[1] = 0; 21 mark[1] = 1; 22 for ( i = 1; i <= n; i++ ) 23 { 24 min = INF; 25 for ( j = 1; j <= n; j++ ) 26 { 27 if ( !mark[j] && within[j] && dist[j] < min ) 28 { 29 k = j; 30 min = dist[j]; 31 } 32 } 33 if( min == INF ) 34 break; 35 mark[k] = 1; 36 dist[k] = min; 37 for ( j = 1; j <= n; j++ ) 38 if ( !mark[j] && within[j] && dist[k] + map[k][j] < dist[j] ) 39 dist[j] = dist[k] + map[k][j]; 40 } 41 42 min = INF; 43 for ( i = 1; i <= n; i++ ) 44 if ( dist[i] + value[i] < min && mark[i] ) 45 min = dist[i] + value[i]; 46 return min; 47 } 48 49 int main() 50 { 51 //freopen("../in.txt","r",stdin); 52 int ranklimit, t, i, j, k; 53 cin >> ranklimit >> n; 54 for ( i = 1; i <= n; i++ ) 55 for ( j = 1; j <= n; j++ ) 56 map[i][j] = ( i == j ? 0 : INF); 57 for ( i = 1; i <= n; i++ ) 58 { 59 cin >> value[i] >> ranks[i] >> t; 60 for ( j = 0; j < t; j++ ) 61 { 62 cin >> k; 63 cin >> map[i][k]; 64 } 65 } 66 67 int min_cost = INF, cost; 68 for ( i = 0; i <= ranklimit; i++ ) 69 { 70 memset(within,0,sizeof(within)); 71 for ( j = 1; j <= n; j++ ) 72 { 73 if ( ranks[j]>=ranks[1]-ranklimit+i && ranks[j]<=ranks[1]+i) 74 within[j] = 1; 75 } 76 cost = Dijkstra (); 77 if ( cost < min_cost ) 78 min_cost = cost; 79 } 80 cout << min_cost << endl; 81 return 0; 82 }
原文：https://www.cnblogs.com/-Ackerman/p/11296952.html