点权拆出来与0号点连边，按照下属→上级的方向建立有向图，跑一个s=0,t=1的单源最短路
限制条件：搜索到的最短路径中，阶级差不超过m
1 #include <queue> 2 #include <vector> 3 #include <cstring> 4 #include <iostream> 5 using namespace std; 6 #define N 105 7 #define INF 1000000 8 struct edge{ 9 int v,w; 10 edge(int v,int w):v(v),w(w){} 11 }; 12 vector<edge>G[N]; 13 int level[N],dis[N],vis[N]; 14 15 #define ifIsUnderTheRestrictionOfLevel if(minLevel<=level[v]&&level[v]<=maxLevel) 16 17 void spfa(int n,int minLevel,int maxLevel){ 18 queue<int>q; 19 fill(dis,dis+n+1,INF),fill(vis,vis+n+1,0); 20 q.push(0),vis[0]=1,dis[0]=0; 21 while(!q.empty()) { 22 int u=q.front();q.pop(),vis[u]=0; 23 for(int i=0;i<G[u].size();i++) { 24 edge&e=G[u][i]; 25 int&v=e.v,w=e.w; 26 ifIsUnderTheRestrictionOfLevel 27 if (dis[v]>dis[u]+w) { 28 dis[v]=dis[u]+w; 29 if(!vis[v])q.push(v),vis[v]=1; 30 } 31 } 32 } 33 } 34 35 int main(){ 36 int m,n; 37 cin>>m>>n; 38 for(int i=1;i<=n;i++){ 39 int P,L,X; 40 cin>>P>>L>>X; 41 level[i]=L; 42 G[0].push_back(edge(i,P)); 43 while(X--){ 44 int T,V; 45 cin>>T>>V; 46 G[T].push_back(edge(i,V)); 47 } 48 } 49 int ans=INF; 50 for(int i=level[1]-m;i<=level[1];i++){ 51 spfa(n,i,i+m); 52 ans=min(ans,dis[1]); 53 } 54 cout<<ans<<endl; 55 return 0; 56 }