oj.uz

Submission #95753

# Submission time Handle Problem Language Result Execution time Memory
95753 2019-02-02T10:10:54 Z easrui None (JOI14_ho_t4) C++14
0 / 100
 144 ms 6876 KB 
#include <bits/stdc++.h>
#define va first
#define vb second
using namespace std;
typedef pair<int,int> pii;
const int MN = 1e5+5;
int N,M,X,H[MN],a,b,t,pos;
long long len,dis,D[MN],h,ans;
vector<pii> G[MN];
struct node{
    int a;
    long long d;
    node(){};
    node(int x, long long y){a = x, d = y;};
    bool operator < (const node &A) const{
        return A.d<d;
    }
};
priority_queue<node> pq;

int main()
{
    //freopen("input.txt","r",stdin);
    ios_base::sync_with_stdio(0),cin.tie(0);
    cin >> N >> M >> X;
    for(int i=1; i<=N; i++) cin >> H[i];
    for(int i=0; i<M; i++){
        cin >> a >> b >> t;
        if(H[a]>=t) G[a].push_back(pii(t,b));
        if(H[b]>=t) G[b].push_back(pii(t,a));
    }
    for(int i=1; i<=N; i++) D[i] = 1e16;
    D[1] = 0;
    pq.push(node(1,0));
    while(!pq.empty()){
        pos = pq.top().a;
        len = pq.top().d;
        pq.pop();
        //cout << pos << ' ' << len << '\n';
        if(len>D[pos]) continue;
        for(pii cur : G[pos]){
            if(len<X){
                h = X - len;
                if(h<cur.va) dis = len + cur.va + (cur.va-h);
                else if(h>H[cur.vb]+cur.va) dis = X - H[cur.vb];
                else dis = len + cur.va;
            } else dis = len + 2*cur.va;
            if(dis<D[cur.vb]){
                D[cur.vb] = dis;
                //cout << cur.vb << '\n';
                pq.push(node(cur.vb,dis));
            }
        }
    }
    ans = D[N]<H[1] ? 2*D[N]+H[N]-H[1] : D[N]+H[N];
    if(D[N]==1e16) ans = -1;
    cout << ans;
}

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 5 ms 2808 KB Output is correct
3 Correct 5 ms 2808 KB Output is correct
4 Correct 4 ms 2808 KB Output is correct
5 Correct 4 ms 2808 KB Output is correct
6 Correct 4 ms 2680 KB Output is correct
7 Correct 4 ms 2680 KB Output is correct
8 Correct 6 ms 2808 KB Output is correct
9 Incorrect 5 ms 2780 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

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

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 5 ms 2808 KB Output is correct
3 Correct 5 ms 2808 KB Output is correct
4 Correct 4 ms 2808 KB Output is correct
5 Correct 4 ms 2808 KB Output is correct
6 Correct 4 ms 2680 KB Output is correct
7 Correct 4 ms 2680 KB Output is correct
8 Correct 6 ms 2808 KB Output is correct
9 Incorrect 5 ms 2780 KB Output isn't correct
10 Halted 0 ms 0 KB -