题解
1 //最短路径——Dijkstra算法
2 //此题的关键在于等级限制的处理，最好的办法是采用枚举，即假设酋长等级为5，等级限制为2，那么需要枚举等级从3~5,4~6,5~7
3 //从满足改等级范围的结点组成的子图中用Dijkstra来算出最短路径
4 //小结，通过枚举的方式可以消除一些图与图之间的限制
C++代码
#include <set> #include <map> #include <queue> #include <stack> #include <cmath> #include <string> #include <vector> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define pi acos(-1.0) #define eps 1e-9 #define fi first #define se second #define rtl rt<<1 #define rtr rt<<1|1 #define bug printf("****** ") #define mem(a,b) memset(a,b,sizeof(a)) #define name2str(x) #x #define fuck(x) cout<<#x" = "<<x<<endl #define f(a) a*a #define sf(n) scanf("%d", &n) #define sff(a,b) scanf("%d %d", &a, &b) #define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c) #define sffff(a,b,c,d) scanf("%d %d %d %d", &a, &b, &c, &d) #define pf printf #define FRE(i,a,b) for(i = a; i <= b; i++) #define FREE(i,a,b) for(i = a; i >= b; i--) #define FRL(i,a,b) for(i = a; i < b; i++)+ #define FRint(i,a,b) for(i = a; i > b; i--) #define FIN freopen("data.txt","r",stdin) #define gcd(a,b) __gcd(a,b) #define lowbit(x) x&-x using namespace std; typedef long long LL; typedef unsigned long long ULL; const int maxn = 205; const int INF = 0x3f3f3f3f; int n,mp[maxn][maxn], k[maxn], dis[maxn]; bool cha[maxn]; bool vis[maxn]; int l[maxn],v[maxn]; int p[maxn]; int minn; int dijkstra() { int minn = INF; memset(vis,false,sizeof(vis)); //清除所有点的标号 for(int i=1;i<=n;i++) dis[i] = INF; //设d[1] = 0,其它为 INF dis[1] = 0; //（此处还未加上进入改点的花费）自己换自己为0 for(int i=1;i<=n;i++) //循环n 次 { int x, m = INF; for(int y=1;y<=n;y++) { //在所有未标号且满足等级限制的点中选出 d值最小的点 x if(!vis[y] && dis[y] <= m && cha[y]) m = dis[x=y]; } vis[x] = true; //标记点x for(int y=1;y<=n;y++) // 对于从x出发的所有边 (x, y)更新dist { if(cha[y]) //若满足等级限制 dis[y] = min(dis[y], dis[x]+mp[x][y]); } } for(int y=1;y<=n;y++) { //对于每个dist[y]还要满足进入改点的花费 dis[y] += p[y]; minn = min(minn,dis[y]); } return minn; //返回最小值 } int main() { int s, e; int size ; cin >> size >> n; //scanf ( "%d%d", &s, &e ); for ( int i = 0; i <= n; i++ ) for ( int j = 0; j <= n; j++ ) mp[i][j] = INF; for(int i = 1;i <= n ; i++){ int x; cin >> p[i] >> l[i] >> x; for(int j = 1;j <= x; j++){ int t , v; cin >> t >> v; mp[i][t] = v; } } minn = INF; int k = l[1]; for(int i=0;i<=size;i++) //枚举 { memset(cha,false,sizeof(cha)); for(int j=1;j<=n;j++) { //枚举等级允许的范围 if(l[j] >=k-size+i && l[j]<=k+i) cha[j] = true; } minn = min(minn, dijkstra()); } cout << minn << endl; return 0; }