题目中一句话:“但是如果他和某个地位较低的人进行了交易,地位较高的的人不会再和他交易,他们认为这样等于是间接接触,反过来也一样。” 个人理解意思是,探险者只能与比自己等级高的人交易或者只能与比自己等级低的人交易,所以,当探险者的初始等级是 k 的时候,他只能选择等级在 [k, k+m] 或者 [k-m, k] 范围内的人交易,但是最后要与酋长交易,所以只能是 [k, k+m] 范围内的人。
#include<bits/stdc++.h>
using namespace std;
const int N = 100+5, inf = 0x3f3f3f3f;
int n, m, low, hig;
int g[N][N], lev[N];
int dis[N];
bool vis[N];
bool check(int k){
return lev[k]>=low && lev[k]<=hig;
}
void dijkstra(){
memset(dis, 0x3f, sizeof dis);
memset(vis, false, sizeof vis);
dis[0] = 0;
for(int i=0; i<=n; i++){
int t = -1;
for(int j=0; j<=n; j++){
if(!vis[j] && (t==-1 || dis[j]<dis[t])) t = j;
}
for(int j=0; j<=n; j++){
if(check(j)) dis[j] = min(dis[j], dis[t]+g[t][j]);
}
vis[t] = true;
}
}
int main(){
scanf("%d%d", &m, &n);
memset(g, 0x3f, sizeof g);
int p, l, x, t, v;
for(int i=1; i<=n; i++){
scanf("%d%d%d", &p, &l, &x);
lev[i] = l, g[0][i] = p;
while(x--){
scanf("%d%d", &t, &v);
g[t][i] = v;
}
}
low = lev[1]-2*m, hig = lev[1]+2*m;
int ans = inf;
for(int i=lev[1]-m; i<=lev[1]; i++){
low = i, hig = i+m;
dijkstra();
ans = min(ans, dis[1]);
}
cout<< ans<< endl;
return 0;
}