fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4.  
  5. using namespace std;
  6.  
  7. const long long INF = 1e18;
  8.  
  9. struct Edge {
  10.     int to;
  11.     int cost;
  12. };
  13.  
  14. // Funkcja realizująca algorytm Dijkstry
  15. void dijkstra(int start, int n, const vector<vector<Edge>>& adj, vector<long long>& dist) {
  16.     dist.assign(n + 1, INF);
  17.     dist[start] = 0;
  18.     priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
  19.     pq.push({0, start});
  20.  
  21.     while (!pq.empty()) {
  22.         long long d = pq.top().first;
  23.         int u = pq.top().second;
  24.         pq.pop();
  25.  
  26.         if (d > dist[u]) continue;
  27.  
  28.         for (auto& edge : adj[u]) {
  29.             if (dist[u] + edge.cost < dist[edge.to]) {
  30.                 dist[edge.to] = dist[u] + edge.cost;
  31.                 pq.push({dist[edge.to], edge.to});
  32.             }
  33.         }
  34.     }
  35. }
  36.  
  37. int main() {
  38.     ios_base::sync_with_stdio(false);
  39.     cin.tie(NULL);
  40.  
  41.     int n;
  42.     if (!(cin >> n)) return 0;
  43.  
  44.     vector<int> prices(n + 1);
  45.     for (int i = 1; i <= n; ++i) {
  46.         cin >> prices[i];
  47.     }
  48.  
  49.     int m;
  50.     cin >> m;
  51.  
  52.     vector<vector<Edge>> adj(n + 1);
  53.     vector<vector<Edge>> adj_rev(n + 1);
  54.  
  55.     for (int i = 0; i < m; ++i) {
  56.         int u, v, c;
  57.         cin >> u >> v >> c;
  58.         adj[u].push_back({v, c});
  59.         adj_rev[v].push_back({u, c});
  60.     }
  61.  
  62.     vector<long long> distTo;   // Złoto -> Metal V
  63.     vector<long long> distFrom; // Metal V -> Złoto
  64.  
  65.     dijkstra(1, n, adj, distTo);
  66.     dijkstra(1, n, adj_rev, distFrom);
  67.  
  68.     long long min_total_cost = INF;
  69.  
  70.     for (int i = 1; i <= n; ++i) {
  71.         // Sprawdzamy tylko metale, do których da się dotrzeć i z których da się wrócić
  72.         if (distTo[i] != INF && distFrom[i] != INF) {
  73.             long long current_cost = distTo[i] + distFrom[i] + (prices[i] / 2);
  74.             if (current_cost < min_total_cost) {
  75.                 min_total_cost = current_cost;
  76.             }
  77.         }
  78.     }
  79.  
  80.     cout << min_total_cost << endl;
  81.  
  82.     return 0;
  83. }
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
4
200
100
40
2
6
1 2 10
1 3 5
2 1 25
3 2 10
3 4 5
4 1 50
stdout
copy 
60
https://ideone.com/dWrAsN
language:
C++14 (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!