oj.uz

Submission #1090864

# Submission time Handle Problem Language Result Execution time Memory
1090864 2024-09-19T00:37:08 Z phong None (JOI14_ho_t4) C++17
0 / 100
 102 ms 25300 KB 
#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 < 0){
                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});
                }
            }
            else{
                if(dp[v] < dp[u] - w){
                    dp[v] = dp[u] - w;
                    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

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

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2652 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 11860 KB Output is correct
2 Correct 88 ms 25300 KB Output is correct
3 Correct 59 ms 13516 KB Output is correct
4 Correct 102 ms 23496 KB Output is correct
5 Correct 80 ms 24176 KB Output is correct
6 Correct 4 ms 2904 KB Output is correct
7 Incorrect 59 ms 9300 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2652 KB Output isn't correct
2 Halted 0 ms 0 KB -