Submission #761634

#	Time	Username	Problem	Language	Result	Execution time	Memory
761634		gggkik	날다람쥐 (JOI14_ho_t4)	C++14	25 / 100	110 ms	19760 KiB

2014_ho_t4

#include <bits/stdc++.h>
using namespace std;
#define ll long long
using pii = pair<int,int>;
const int MXN = 1e5+5;
vector<pii> E[MXN];
ll h[MXN], d[MXN];
int n,m,s;
void dijkstra(int x){
    priority_queue<pii> pq; pq.push({0,x});
    for(int i = 2;i<=n;i++) d[i] = 1LL<<62;
    for(;pq.size();){
        x = pq.top().second; pq.pop();
        for(auto i : E[x]) if(h[x]>=i.second && d[i.first]>d[x]+i.second*2){
            d[i.first] = d[x]+i.second*2;
            pq.push({-d[i.first],i.first});
        }
    }
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m >> s;
    for(int i = 1;i<=n;i++) cin >> h[i];
    for(int i = 0;i<m;i++){
        int a,b,c; cin >> a >> b >> c;
        E[a].push_back({b,c});
        E[b].push_back({a,c});
    }
    dijkstra(1);
    if(d[n]==1LL<<62) cout << -1;
    else cout << d[n]+h[n];
}

• Subtask 1: 0 / 25
• Subtask 2: 25 / 25
• Subtask 3: 0 / 50