Untitled

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
const long long INF = 200000000;

struct WD
{
    int next;
    long long water;
    long long dist;
};

struct cmp{
    bool operator()(const WD &a, const WD &b){
        if(a.dist!=b.dist){
            return a.dist<b.dist;
        }
        return a.water>b.water;
    }
};

int waters[100001];
long long dp[100001];
long long dp_water[100001];
vector<WD> graph[100001];
int town, road, target;

void dijstra(int start, int target){
    // 거리의 최소 with 물의 max 
    priority_queue<WD, vector<WD>, cmp> pq;
    fill(dp, dp+100001, INF);
    dp[start] = 0; // 
    dp_water[start] = waters[start];
    pq.push({start,dp_water[start],dp[start]});
    while(!pq.empty()){
        WD cur = pq.top();
        int cur_idx = cur.next;
        long long cur_dist = cur.dist;
        long long cur_water = cur.water;
        pq.pop();
        if(dp[cur_idx] < cur_dist) continue;
        for(WD next_node : graph[cur_idx]){
            int next_idx = next_node.next;
            long long next_dis = cur_dist + next_node.dist;
            long long next_wat = cur_water + next_node.water;
            if((next_dis<=dp[next_idx]) || (next_dis == dp[next_idx] && dp_water[next_idx] < next_wat)){
                dp_water[next_idx] = next_wat;
                dp[next_idx] = next_dis;
                pq.push({next_idx,dp_water[next_idx],next_dis});
            }
        }
    }

    if(dp[target]!=INF){
        printf("%lld %lld\n",dp[target], dp_water[target]);
        return;
    }
    printf("-1\n");
    return;
}

int main(void){
    // ios::sync_with_stdio(false);cin.tie(0);
    scanf("%d",&town);
    for(int i = 1;i<=town;i++){
        scanf("%d",&waters[i]);
    }
    scanf("%d", &road);
    int start, arrive;
    long long dis;
    while(road--){
        scanf("%d %d %lld", &start, &arrive, &dis);
        graph[start].push_back({arrive,waters[start],dis});
    }
    cin >> start >> target;
    dijstra(start,target);
}c