# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
95324 | Retro3014 | 날다람쥐 (JOI14_ho_t4) | C++17 | 313 ms | 27584 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <vector>
#include <algorithm>
#include <stdio.h>
#include <queue>
using namespace std;
#define MAX_N 100000
#define MAX_M 300000
#define INF 1000000000000000000LL
typedef long long ll;
int N, M;
struct S{
int idx;
ll data;
};
vector<S> gp[MAX_N+1];
ll H[MAX_N+1];
ll X;
struct S2{
S2 (int idx, ll h, ll t) : idx(idx), h(h), t(t) {}
int idx;
ll h, t;
bool operator <(const S2 &a)const{
return t>a.t;
}
};
priority_queue<S2> pq;
ll dist[MAX_N+1];
ll dist2[MAX_N+1];
ll ans = INF;
int main(){
scanf("%d%d%lld", &N, &M, &X);
for(int i=1; i<=N; i++){
scanf("%lld", &H[i]);
}
for(int i=0; i<M; i++){
int a, b;
ll c;
scanf("%d%d%lld", &a, &b, &c);
gp[a].push_back({b, c}); gp[b].push_back({a, c});
}
for(int i=1; i<=N; i++) dist[i] = dist2[i] = INF;
pq.push({1, X, 0});
if(X==0) dist[1] = 0;
else dist2[1] = 0;
while(!pq.empty()){
S2 now = pq.top(); pq.pop();
if(now.idx==N){
ans = min(ans, now.t+H[N]-now.h);
}
if(now.h==0){
if(dist[now.idx]!=now.t) continue;
for(int i=0; i<gp[now.idx].size(); i++){
if(gp[now.idx][i].data>H[now.idx]) continue;
int nxt = gp[now.idx][i].idx;
if(dist[nxt]>dist[now.idx]+gp[now.idx][i].data*2){
dist[nxt] = dist[now.idx]+gp[now.idx][i].data*2;
pq.push({nxt, (ll)0, dist[nxt]});
}
}
}else{
if(dist2[now.idx]!=now.t) continue;
for(int i=0; i<gp[now.idx].size(); i++){
int nxt = gp[now.idx][i].idx;
if(gp[now.idx][i].data<now.h){
if(now.h-gp[now.idx][i].data>H[nxt]){
if(dist2[nxt]>now.t+gp[now.idx][i].data+now.h-gp[now.idx][i].data-H[nxt]){
dist2[nxt] = now.t+gp[now.idx][i].data+now.h-gp[now.idx][i].data-H[nxt];
pq.push({nxt, H[nxt], dist2[nxt]});
}
}
else{
if(dist2[nxt]>now.t+gp[now.idx][i].data){
dist2[nxt] = now.t+gp[now.idx][i].data;
pq.push({nxt, now.h-gp[now.idx][i].data, dist2[nxt]});
}
}
}else{
if(gp[now.idx][i].data>H[now.idx]) continue;
if(dist[nxt]>now.t+gp[now.idx][i].data*2-now.h){
dist[nxt] = now.t+gp[now.idx][i].data*2-now.h;
pq.push({nxt, 0, dist[nxt]});
}
}
}
}
}
if(ans==INF) printf("-1");
else printf("%lld", ans);
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |