Submission #1090865

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090865		phong	날다람쥐 (JOI14_ho_t4)	C++17	100 / 100	107 ms	24184 KiB

2014_ho_t4

#include<bits/stdc++.h>
#define ll long long
const int nmax = 1e5 + 5, N = 1e5;
const ll oo = 1e18 + 5, base = 311;
const int lg = 17,mod = 1e9 +7;
#define pii pair<ll, ll>
#define fi first
#define se second
#define endl "\n"
#define debug(a, n) for(int i = 1; i <= n; ++i) cout << a[i] << ' '; cout << "\n";
using namespace std;

int n, m, X, a[nmax];
struct node{
    ll w, u, x, id;
    friend bool operator < (const node&a, const node&b){
        return a.w > b.w;
    }
};
ll dp[nmax];
vector<pii> adj[nmax];
int cnt[nmax];

main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
//    freopen("ROBOT.inp", "r", stdin);
//    freopen("ROBOT.out", "w", stdout);
    cin >> n >> m >> X;
    for(int i = 1; i <= n; ++i) cin >> a[i];
    for(int i =1; i <= m; ++i){
        int u, v, w;
        cin >> u >> v >> w;
        if(a[u] >= w)  adj[u].push_back({w, v});
        if(a[v] >= w)adj[v].push_back({w, u});

    }
    priority_queue<pii> q;
    for(int i = 1; i <= n; ++i) dp[i] = -oo;
    dp[1] = X;
    q.push({X, 1});
    while(q.size()){
        pii tmp = q.top();q.pop();
        int u = tmp.se;
        for(auto [w,v] : adj[u]){
            if(tmp.fi - w <= a[v]){
                if(dp[v] < dp[u] - w){
                    dp[v] = dp[u] - w;
                    q.push({dp[v], v});
                }
            }
            else if(tmp.fi - w > a[v]){
                if(dp[v] < a[v]){
                    dp[v] = a[v];
                    q.push({dp[v], v});
                }
            }
        }
    }
    if(dp[n] == -oo) cout << -1;
    else cout << X - dp[n] +  abs(a[n] - dp[n]);
}
/*
3 3

899
*/

Compilation message (stderr)

2014_ho_t4.cpp:24:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   24 | main(){
      | ^~~~

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