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
思路：我看网上的写法是 酋长等级为Q ，则可行区间为 【Q-m，Q】 ...... 【Q，Q+m】，枚举每个区间，然后不在区间内的点就不加入最短路，跑m遍最短路
我用了另一种写法，总感觉有点搜索的意思，在优先队列中存入的结构体中记录当前路径所走过的最高等级和最低等级，超过m就放弃这路径，否则更新
1 #include<cstdio> 2 #include<cstring> 3 #include<queue> 4 using namespace std; 5 6 int m,n; 7 struct Node 8 { 9 int s; 10 int low,high; 11 int val; 12 Node(int s=0,int low=0,int high=0,int val=0):s(s),low(low),high(high),val(val){} 13 bool operator<(const Node x)const 14 { 15 return val > x.val; 16 } 17 }; 18 19 struct N 20 { 21 int y; 22 int next; 23 int val; 24 }node[10005]; 25 26 int cnt,head[105],level[105]; 27 void add(int x,int y,int val) 28 { 29 node[++cnt].y=y; 30 node[cnt].val =val; 31 node[cnt].next=head[x]; 32 head[x]=cnt; 33 } 34 35 priority_queue<Node>que; 36 int dist[105]; 37 bool vis[105]; 38 void dijstra() 39 { 40 while(!que.empty())que.pop(); 41 que.push(Node(0,level[1],level[1],0)); 42 memset(dist,0x3f,sizeof(dist)); 43 while(!que.empty()) 44 { 45 Node tmp = que.top(); 46 que.pop(); 47 if(vis[tmp.s])continue; 48 vis[tmp.s]=1; 49 dist[tmp.s] = tmp.val; 50 for(int i=head[tmp.s];i;i=node[i].next) 51 { 52 int to = node[i].y; 53 int low = min(tmp.low,level[to]); 54 int high = max(tmp.high,level[to]); 55 if(dist[to] > tmp.val + node[i].val && high - low <= m) 56 { 57 que.push(Node(to,low,high,tmp.val+node[i].val)); 58 } 59 } 60 61 } 62 } 63 64 int main() 65 { 66 scanf("%d%d",&m,&n); 67 for(int i=1;i<=n;i++) 68 { 69 int p,l,x; 70 scanf("%d%d%d",&p,&l,&x); 71 level[i] = l; 72 add(0,i,p); 73 for(int j=1;j<=x;j++) 74 { 75 int t,num; 76 scanf("%d%d",&t,&num); 77 add(t,i,num); 78 } 79 } 80 dijstra(); 81 printf("%d\n",dist[1]); 82 }
原文：https://www.cnblogs.com/iwannabe/p/10727011.html
