| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 154047 | mhy908 | 날다람쥐 (JOI14_ho_t4) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define llinf 8987654321987654321
#define inf 1987654321
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
int h[100010];
LL dist[100010];
vector<int> link[100010], c[100010];
int n, m, x;
priority_queue<pair<LL, int> > q;
int main(){
scanf("%d %d %d",&n, &m, &x);
for(int i=1; i<=n; i++) scanf("%d", &h[i]);
for(int i=1; i<=m; i++){
int a, b, t;
scanf("%d %d %d", &a, &b, &t);
if(h[a]>=t){
link[a].pb(b);
c[a].pb(t);
}
if(h[b]>=t){
link[b].pb(a);
c[b].pb(t);
}
}
for(int i=1; i<=n; i++)dist[i]=-llinf;
q.push({-(LL)x, -1});
while(!q.empty()){
int now=-q.top().S;
LL dis=-q.top().F;
q.pop();
if(dist[now]>=dis)continue;
dist[now]=dis;
for(int i=0; i<link[now].size(); i++){
int u=link[now][i], co=c[now][i];
//printf("%lld %d\n", min(dis-co, (LL)h[u]), u);
if(c>h[now])continue;
q.push({-min(dis-co, (LL)h[u]), -u});
}
}
//for(int i=1; i<=n; i++)printf("%lld ", dist[i]);
if(dist[n]==-llinf)puts("-1");
else printf("%lld", x+h[n]-dist[n]*2);
}