本文主要是介绍hdu5361（2015多校6）--In Touch（变形的dijkstra），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：点击打开链接
题目大意：给出一个n个数的序列，标号为1到n，对于第i个数，它可以移动到距离i为[ li,ri ]的位置，花费为c[i]，输入三行，第一行l[i]，第二行r[i]，第三行c[i],现在问对于第一个数来说，它移动到第i个位置的最小花费。（1<=i<=n）
这是一个每个点可以移动到一段中任意一个点，并且花费一样，这样就不适用与已有的四种最短路，但是可以对dijkstra进行变形，dij是每次找到一个距离最小的节点，用这个节点去更新其它节点，我们可以用一个优先队列，每次找到一个点，用这个点去更新其他的点，这个点要满足 dis[i]+c[i]是最小的，那么这个点更新出来的点也就是最小的。
有优先队列维护dis+c的值，用set来找到一段中还没有更新的点，这样就可以防止会遍历到已经更新好的点，造成超时。
#include <cstdio>
#include <cstring>
#include <queue>
#include <set>
#include <algorithm>
using namespace std ;
#define LL __int64
#pragma comment(linker, "/STACK:102400000,102400000")
struct node{int id ;LL c ;bool operator < (node a) const {return c > a.c ;}
} p , q ;
priority_queue<node> que ;
set<int> s ;
set<int> ::iterator iter ;
LL dis[200010] , c[200010] ;
int l[200010] , r[200010] ;
void f(int l,int r) {iter = s.lower_bound(l) ;while( iter != s.end() ) {if( *iter > r ) break ;dis[ *iter ] = p.c ;q.id = *iter ;q.c = p.c + c[ q.id ] ;que.push( q ) ;iter++ ;s.erase(q.id) ;}return ;
}
int main() {int t , n , i , x , y ;//freopen("1009.in","r",stdin) ;//freopen("111.out","w",stdout) ;scanf("%d", &t) ;while( t-- ) {while( !que.empty() ) que.pop() ;memset(dis,-1,sizeof(dis)) ;s.clear() ;scanf("%d", &n) ;for(i = 2 ; i <= n ; i++) s.insert(i) ;for(i = 1 ; i <= n ; i++) scanf("%d", &l[i]) ;for(i = 1 ; i <= n ; i++) scanf("%d", &r[i]) ;for(i = 1 ; i <= n ; i++) scanf("%I64d", &c[i]) ;dis[1] = 0 ;p.id = 1 ;p.c = c[1] ;que.push(p) ;while( !que.empty() && !s.empty() ) {p = que.top() ;que.pop() ;x = max(p.id - r[ p.id ],1) ;y = p.id - l[ p.id ] ;if( y >= 1 ) f(x,y) ;x = p.id + l[ p.id ] ;y = min(p.id + r[ p.id ],n) ;if( x <= n ) f(x,y) ;}for(i = 1 ; i < n ; i++)printf("%I64d ", dis[i]) ;printf("%I64d\n", dis[i]) ;}return 0 ;
}
这篇关于hdu5361（2015多校6）--In Touch（变形的dijkstra）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
