oj.uz

Submission #140378

# Submission time Handle Problem Language Result Execution time Memory
140378 2019-08-02T16:52:38 Z nhc7502 None (JOI14_ho_t4) C++14
0 / 100
 375 ms 31892 KB 
///EVERYONE BELIEVE IN GODTAEGYU
#include<bits/stdc++.h>
using namespace std;
const long long INF = 1e15;
long long n, m, i, j, k;
long long x, h[100141];
long long dist[100141];
vector<pair<int,int>>graph[100141];
priority_queue<pair<long long, int>>pq;

int main(){
	iostream::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	for(cin>>n>>m>>x; i++<n;)
	{
		cin>>h[i];
		dist[i] = -INF;
	}
	for(;m--;)
	{
		cin>>i>>j>>k;
		if(h[i] >= k)
			graph[i].push_back({j, k});
		if(h[j] >= k)
			graph[j].push_back({i, k});
	}
	pq.push({x, 1});
	while(!pq.empty())
	{
		tie(m, i) = pq.top();
		pq.pop();
		if(dist[i] != -INF)continue;
		dist[i] = m;
		for(auto next : graph[i])
		{	//i = 현재 나무, m = 현재 높이, j = 다음 나무, k = 다음 나무 거리
			tie(j, k) = next;
			pq.push({min(m - k, h[j]), j});
		}
	}
	if(dist[n] == INF) cout<<-1;
	else cout<<x + h[n] - dist[n] * 2;
	/*
	if 양수 -> 유지할 수 있는 최소 높이
	따라서 (x-dist[n]) + (h[n]-dist[n])
	if 음수 -> x는 다 쓴 이후 나무사이 가는데 최소거리(올라가는거 고려 X)
	따라서 (h[n]-dist[n]) -> 올라가는데 필요한 비용
	x-dist[n] -> 날아가는데 필요한 비용
	*/
	return 0;
}

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 2808 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 7800 KB Output is correct
2 Correct 335 ms 24824 KB Output is correct
3 Correct 180 ms 12260 KB Output is correct
4 Correct 375 ms 23696 KB Output is correct
5 Correct 359 ms 31892 KB Output is correct
6 Correct 10 ms 3044 KB Output is correct
7 Incorrect 111 ms 9604 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 2808 KB Output isn't correct
2 Halted 0 ms 0 KB -