#include <stdio.h> #include <iostream> #include <vector> #include <queue> using namespace std; #define INF 1000000000000 vector<pair<int, int>> graph[100010]; long long d_up[100010]; long long d_down[100010]; int height[100010]; int V, E; int happy, strength; void dijkstra_up(int start) { priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq; pq.push({0, start}); d_up[start] = 0; while(!pq.empty()) { int now = pq.top().second; long long nowCost = pq.top().first; pq.pop(); if(nowCost != d_up[now]) { continue; } for(int i = 0; i < graph[now].size(); i++) { int next = graph[now][i].first; long long nextCost = graph[now][i].second; if(height[now] < height[next]) { if(nowCost + nextCost < d_up[next]) { d_up[next] = nowCost + nextCost; pq.push({d_up[next], next}); } } } } } void dijkstra_down(int start) { priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq; pq.push({0, start}); d_down[start] = 0; while(!pq.empty()) { int now = pq.top().second; long long nowCost = pq.top().first; pq.pop(); if(nowCost != d_down[now]) { continue; } for(int i = 0; i < graph[now].size(); i++) { int next = graph[now][i].first; long long nextCost = graph[now][i].second; if(height[now] < height[next]) { if(nowCost + nextCost < d_down[next]) { d_down[next] = nowCost + nextCost; pq.push({d_down[next], next}); } } } } } int main(void) { // freopen("B16681_input.txt", "r", stdin); cin >> V >> E >> strength >> happy; for(int i = 1; i <= V; i++) { cin >> height[i]; d_up[i] = INF; d_down[i] = INF; } for(int i = 1; i <= E; i++) { int from, to, weight; cin >> from >> to >> weight; graph[from].push_back({to, weight}); graph[to].push_back({from, weight}); } dijkstra_up(1); dijkstra_down(V); long long Max = -INF; for(int i = 2; i < V; i++) { if(Max < happy*height[i] - strength*d_up[i] - strength*d_down[i]) { Max = happy*height[i] - strength*d_up[i] - strength*d_down[i]; } } if(Max == -INF) { cout << "Impossible"; } else { cout << Max; } return 0; } | cs |
'Baekjoon > Graph' 카테고리의 다른 글
[백준 6118] 숨바꼭질 (Dijkstra) (C/C++) (0) | 2020.05.17 |
---|---|
[백준 5719] 거의 최단경로 (Dijkstra) (C/C++) (★★★) (0) | 2020.02.19 |
[백준 2211] 네트워크 복구 (Dijkstra) (C/C++) (0) | 2020.02.18 |
[백준 1504] 특정한 최단경로 (Floyd-Warshall) (C/C++) (0) | 2020.02.17 |
[백준 1238] 파티 (Floyd-Warshall) (C/C++) (0) | 2020.02.17 |