Untitled

33
mail@pastecode.io avatar
unknown
c_cpp
a year ago
2.0 kB
2
Indexable
Never
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
const long INF = 200000000;

struct WD
{
    int next;
    long water;
    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;
    }
};

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

void dijstra(int start, int target){
    priority_queue<WD, vector<WD>, cmp> pq;
    // 거리의 최소 with 물의 max 
    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;
        int cur_dist = cur.dist;
        pq.pop();
        if(dp[cur_idx] < cur.dist) continue;
        int cur_water = cur.water;
        for(int i=0, size = graph[cur_idx].size(); i<size;i++){
            WD next_node = graph[cur_idx][i];
            int next_idx = next_node.next;
            if((dp[next_idx] > next_node.dist + cur_dist) || (next_node.dist + cur_dist == dp[next_idx] && (dp_water[next_idx]< next_node.water + cur_water)) ){
                dp[next_idx] = next_node.dist + cur_dist;
                dp_water[next_idx] = next_node.water + cur_water;
                pq.push({next_idx,dp_water[next_idx],dp[next_idx]});
            }
        }
    }

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

int main(void){
    scanf("%d",&town);
    for(int i = 1;i<=town;i++){
        scanf("%ld",&waters[i]);
    }
    scanf("%d",&road);
    while(road--){
        scanf("%d %d %d", &start, &arrive, &dis);
        graph[start].push_back({arrive,waters[start],dis});
        graph[arrive].push_back({start,waters[arrive], dis});
    }
    cin >> start >> target;
    dijstra(start,target);
}