本文主要是介绍hdu5385（2015多校8）--The path（贪心，搜索），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：点击打开链接
题目大意：给出一个有向图，求1到其它点的最短距离，要求dis[1] < dis[2]....dis[x] ... > dis[n-1] > dis[n] (1 < x <= n)
给出符合条件的每条边的边长(1<=边长<=n)
设置vis标记点是否已经存在，从左边开始逐个搜索，如果点已经存在那么继续遍历，否则换方向遍历（从右开始遍历），因为题目保证存在输出，所以一定可以遍历完所有的。
按照被遍历到的时间也就是dis的值，然后在按照(u,v) = abs(dis[u]-dis[v])，推出边的长度。
注意边的长度是1到n，如果值是0，也是设为n
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std ;
#define maxn 100010
struct node{int u , v , next ;
}edge[maxn] , p[maxn] ;
int head[maxn] , cnt ;
int vis[maxn] , dis[maxn] , num , n , l , r ;
void add(int u,int v) {edge[cnt].v = v ; edge[cnt].next = head[u] ;head[u] = cnt++ ;
}
void solve(int &i,int k) {while( i > 0 && i <= n ) {if( !vis[i] ) return ;if( dis[i] != -1 ) return ;dis[i] = num++ ;for(int j = head[i] ; j != -1 ; j = edge[j].next) {vis[edge[j].v] = 1 ;}i += k ;}
}
int main() {int t , m , v , i , j , k ;//freopen("1006.in","r",stdin) ;//freopen("111.out","w",stdout) ;scanf("%d", &t) ;while( t-- ) {scanf("%d %d", &n, &m) ;memset(head,-1,sizeof(head)) ;memset(vis,0,sizeof(vis)) ;memset(dis,-1,sizeof(dis)) ;cnt = 0 ;for(i = 0 ; i < m ; i++) {scanf("%d %d", &p[i].u, &p[i].v) ;add(p[i].u,p[i].v) ;}vis[1] = 1 ;l = 1 ; r = n ;num = 0 ;while(l <= r) {solve(l,1) ;solve(r,-1) ;}for(i = 0 ; i < m ; i++) {k = abs(dis[ p[i].u ]-dis[ p[i].v ]) ;if( !k ) k = n ;printf("%d\n", k ) ;}}return 0 ;
}
这篇关于hdu5385（2015多校8）--The path（贪心，搜索）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
