oj.uz

Submission #55154

# Submission time Handle Problem Language Result Execution time Memory
55154 2018-07-06T06:56:50 Z 윤교준(#1528) None (JOI14_ho_t4) C++11
25 / 100
 1493 ms 17480 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;
	}
	
	upmin(Ans, f(0));
	upmin(Ans, f(X));
	upmin(Ans, f(MXH));

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

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2808 KB Output is correct
2 Correct 8 ms 3020 KB Output is correct
3 Incorrect 9 ms 3124 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 767 ms 10528 KB Output is correct
2 Correct 1030 ms 16832 KB Output is correct
3 Correct 1313 ms 16832 KB Output is correct
4 Correct 807 ms 17480 KB Output is correct
5 Correct 895 ms 17480 KB Output is correct
6 Correct 12 ms 17480 KB Output is correct
7 Correct 190 ms 17480 KB Output is correct
8 Correct 1493 ms 17480 KB Output is correct
9 Correct 444 ms 17480 KB Output is correct
10 Correct 152 ms 17480 KB Output is correct
11 Correct 198 ms 17480 KB Output is correct
12 Correct 431 ms 17480 KB Output is correct
13 Correct 95 ms 17480 KB Output is correct
14 Correct 263 ms 17480 KB Output is correct
15 Correct 22 ms 17480 KB Output is correct
16 Correct 370 ms 17480 KB Output is correct
17 Correct 104 ms 17480 KB Output is correct
18 Correct 105 ms 17480 KB Output is correct
19 Correct 75 ms 17480 KB Output is correct
20 Correct 155 ms 17480 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2808 KB Output is correct
2 Correct 8 ms 3020 KB Output is correct
3 Incorrect 9 ms 3124 KB Output isn't correct
4 Halted 0 ms 0 KB -