HDU 1568 Legal path (DP)

제목: LINK
제목: 방향도를 정하고 1->n의'최단로'를 구한다.이곳의'최단로'는 한정된 조건이 있다. 바로 최단로의 각 변의 권한이 이전 변(있으면)보다 적어도 k가 크다.포인트 n1e5, 변수 m2e5가 비교적 크다.DP의 해법을 고려할 수 있습니다.모든 변을 권한 크기에 따라 정렬할 수 있는데 가장 쉽게 떠오르는 것은 O(m^2)의 해법이다.이렇게 하면 중간에 쓸모없는 가장자리가 많이 널려 있기 때문에 우리는 최적화를 해야 한다.우리는 직접적인 변 i, j를 통해 x점에 도달할 수 있다. 만약에 권한값val[i]> val[j]이 있다면 반드시 x점까지의 최단거리 dis[i]v)를 이용하여 이동할 때 u의 상태 dp[u]에서 변권이 x.val-k보다 작으면 변권이 가장 큰 것(그의 최단길은 틀림없이 안에서 가장 작은 것)이다. 이 과정은 2분을 이용할 수 있다. 만약에 그의 최단길 +x.val이 v점의 다른 변권치보다 작은 변에서 이동한 최단길이 모두 작다면 남는다.상세한 것은 코드를 보십시오.

/* ***********************************************
 Author        :Napoleon
 Created Time  :2015-01-31 18:29:48
 Problem       :bc 28 c dp
************************************************ */
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std; 
#define INF 1000000000
typedef __int64 LL; 
#define N 233333
int t, n, m, k; 
struct node {
	int u, v, w; 
}edge[N]; 
vector > dp[N]; 
int cmp(node x, node y) {
	return x.w < y.w; 
}
int gao(int id, int ma) {
	int l = 0, r = dp[id].size() - 1, m; 
	int ret = -1; 
	while(l <= r) {
		m = (l + r) >> 1; 
		if(dp[id][m].first <= ma) {
			l = m + 1; ret = m; 
		}
		else r = m - 1; 
	}
	return ret; 
}
int main() {
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin); 
#endif // ONLINE_JUDGE
	scanf("%d", &t); 
	while(t--) {
		scanf("%d%d%d", &n, &m, &k); 
		for(int i = 1;i <= m; i++) {
			scanf("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].w); 
		}
		sort(edge+1, edge+1+m, cmp); 
		for(int i = 0; i <= n; i++) dp[i].clear(); 
		int last = 0 ;
		dp[1].push_back(make_pair(-1, 0)); 
		for(int i = 1; i <= m; i++) {
			// printf("%d %d : %d 
", edge[i].u, edge[i].v, edge[i].w); 
			while(last + 1 <= m && edge[last + 1].w + k <= edge[i].w) last ++; 
			int u = edge[i].u, v = edge[i].v, w = edge[i].w; 
			int x = gao(u, last); 
			if(x == -1) continue; 
			int vsize = dp[v].size(); 
			if(vsize == 0 || dp[v][vsize - 1].second > dp[u][x].second + w) {
				dp[v].push_back(make_pair(i, dp[u][x].second + w)); 
			}
		}
		int size = dp[n].size(); 
		if(size == 0) puts("-1"); 
		else printf("%I64d
", dp[n][size - 1].second); 
	}
	return 0; 
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

[BOJ]11048(python)

python 풀이 DP를 이용해 풀이 보통 이런 문제는 dfs나 bfs로 풀이하는 것이여서 고민을 했는데 이 문구 덕분에 DP 를 이용해 풀이할 수 있었다 뒤로 돌아가는 등의 경우를 고려하지 않아도 되기 때문이다 코...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

HDU 1568 Legal path (DP)

좋은 웹페이지 즐겨찾기