oj.uz

답안 #55153

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
55153 2018-07-06T06:53:16 Z 윤교준(#1528) 날다람쥐 (JOI14_ho_t4) C++11
25 / 100
 1306 ms 17356 KB 
#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define befv(V) ((V)[sz(V)-2])
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define upmax(a,b) (a)=max((a),(b))
#define upmin(a,b) (a)=min((a),(b))
#define rb(x) ((x)&(-(x)))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;

const int MAXN = 100005;
const int MAXM = 300005;

vector<pii> G[MAXN];

ll D[MAXN];

int A[MAXM], B[MAXM], C[MAXM];

int H[MAXN];

ll Ans = INFLL;
int N, M, X, MXH;

ll f(int h) {
	priority_queue<pli, vector<pli>, greater<pli>> PQ;

	fill(D, D+N+1, INFLL);
	D[1] = 0;
	PQ.push(pli(0, 1));

	for(; !PQ.empty();) {
		int idx; ll dst; tie(dst, idx) = PQ.top(); PQ.pop();
		if(D[idx] < dst) continue;

		for(pii e : G[idx]) {
			int nidx = e.first; ll ndst = dst + e.second;
			if(H[nidx] < ll(h) - ndst) continue;
			if(D[nidx] <= ndst) continue;
			D[nidx] = ndst;
			PQ.push(pli(ndst, nidx));
		}
	}

	return D[N]*2 + abs(X - h) + H[N] - h;
}

int main() {
    //freopen("input.txt", "r", stdin);
	ios::sync_with_stdio(false);

	cin >> N >> M >> X;
	for(int i = 1; i <= N; i++) cin >> H[i];
	for(int i = 1; i <= M; i++) cin >> A[i] >> B[i] >> C[i];

	for(int i = 1, a, b, c; i <= M; i++) {
		a = A[i]; b = B[i]; c = C[i];
		if(c <= H[a]) G[a].eb(b, c);
		if(c <= H[b]) G[b].eb(a, c);
	}

	if(INFLL <= f(0)) {
		puts("-1");
		return 0;
	}

	{
		int s = 0, e = H[1]; for(int m; s < e;) {
			m = (s+e+1)/2;
			if(INFLL <= f(m)) e = m-1;
			else s = m;
		}

		MXH = s;
	}

	{
	    int s = 0, e = min(X, MXH); for(int m; 3 < e-s;) {
			m = (s+e)/2;
			ll t1 = f(m), t2 = f(m+1);
			if(t1 > t2) s = m+1;
			else e = m;
	    }
		
		for(int i = s; i <= e; i++)
			upmin(Ans, f(i));
	}
	
	upmin(Ans, f(X));

	cout << Ans << endl;
	return 0;
}

Subtask #1
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2808 KB Output is correct
2 Correct 8 ms 3048 KB Output is correct
3 Incorrect 9 ms 3048 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 466 ms 10568 KB Output is correct
2 Correct 800 ms 16784 KB Output is correct
3 Correct 857 ms 16784 KB Output is correct
4 Correct 532 ms 17356 KB Output is correct
5 Correct 747 ms 17356 KB Output is correct
6 Correct 11 ms 17356 KB Output is correct
7 Correct 110 ms 17356 KB Output is correct
8 Correct 1306 ms 17356 KB Output is correct
9 Correct 298 ms 17356 KB Output is correct
10 Correct 82 ms 17356 KB Output is correct
11 Correct 99 ms 17356 KB Output is correct
12 Correct 237 ms 17356 KB Output is correct
13 Correct 70 ms 17356 KB Output is correct
14 Correct 172 ms 17356 KB Output is correct
15 Correct 17 ms 17356 KB Output is correct
16 Correct 268 ms 17356 KB Output is correct
17 Correct 61 ms 17356 KB Output is correct
18 Correct 51 ms 17356 KB Output is correct
19 Correct 49 ms 17356 KB Output is correct
20 Correct 62 ms 17356 KB Output is correct

Subtask #3
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2808 KB Output is correct
2 Correct 8 ms 3048 KB Output is correct
3 Incorrect 9 ms 3048 KB Output isn't correct
4 Halted 0 ms 0 KB -