oj.uz

답안 #55160

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
55160 2018-07-06T07:20:16 Z 김세빈(#1527) 도넛 (JOI14_ho_t3) C++11
0 / 100
 4 ms 2680 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll,ll> pll;

vector <pll> E[101010];
priority_queue <pll> Q;
ll H[101010], D[101010], F[101010];
bool chk[101010];
ll n, s;

int main()
{
	ll m, a, b, c, i;
	pll p;
	
	scanf("%lld%lld%lld", &n, &m, &s);
	
	for(i=1;i<=n;i++){
		scanf("%lld", H+i);
		D[i] = 1e18;
	}
	
	for(;m--;){
		scanf("%lld%lld%lld", &a, &b, &c);
		E[a].push_back(pll(b, c));
		E[b].push_back(pll(a, c));
	}
	
	Q.push(pll(0, 1));
	
	for(;!Q.empty();){
		p = Q.top(); Q.pop();
		if(chk[p.second]) continue;
		
		chk[p.second] = 1;
		D[p.second] = -p.first;
		
		for(auto t: E[p.second]){
			if(!chk[t.first] && (s + p.first) >= t.second){
				if(s + p.first - t.second > H[t.first]) Q.push(pll(H[t.first] - s, t.first));
				else Q.push(pll(p.first - t.second, t.first));
			}
		}
	}
	
	for(i=1;i<=n;i++){
		if(chk[i]){
			F[i] = s;
			
			for(auto t: E[i]){
				if(!chk[t.first] && t.second <= H[i]){
					Q.push(pll(s - D[i] * 2 - t.second * 2, t.first));
				}
			}
		}
	}
	
	for(;!Q.empty();){
		p = Q.top(); Q.pop();
		if(chk[p.second]) continue;
		
		chk[p.second] = 1;
		F[p.second] = -p.first;
		
		for(auto t: E[p.second]){
			if(!chk[t.first] && t.second <= H[p.second]){
				Q.push(pll(p.first - t.second * 2, t.first));
			}
		}
	}
	
	if(chk[n]) printf("%lld\n", min(D[n] + H[n] - (s - D[n]), F[n] + H[n]));
	else printf("-1\n");
	
	return 0;
}

Compilation message

2014_ho_t3.cpp: In function 'int main()':
2014_ho_t3.cpp:19:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld%lld", &n, &m, &s);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
2014_ho_t3.cpp:22:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", H+i);
   ~~~~~^~~~~~~~~~~~~
2014_ho_t3.cpp:27:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld%lld", &a, &b, &c);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 2680 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 2680 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 2680 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 2680 KB Output isn't correct
2 Halted 0 ms 0 KB -