fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define ll long long
  6.  
  7. #define EGRY                          \
  8.     ios_base::sync_with_stdio(false); \
  9.     cin.tie(NULL);
  10.  
  11. const int MAX = 2 * 1e5 + 1000;
  12. const int MOD = 1e9 + 7;
  13. const ll OO = LLONG_MAX;
  14.  
  15. const double EPS = (double)1e-9;
  16.  
  17. struct Edge {
  18.     int to;
  19.     ll weight;
  20. };
  21.  
  22. struct Taxi {
  23.     ll maxDistance, cost;
  24. };
  25.  
  26. int n, m, start, destination;
  27. vector<vector<Edge>> graph;
  28. vector<Taxi> taxis;
  29.  
  30. vector<ll> dijkstra(int src) {
  31.     vector<ll> dist(n + 1, OO);
  32.     priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq;
  33.  
  34.     dist[src] = 0;
  35.     pq.push({0, src});
  36.  
  37.     while (!pq.empty()) {
  38.         auto [currDist, u] = pq.top();
  39.         pq.pop();
  40.  
  41.         if (currDist > dist[u]) continue;
  42.  
  43.         for (auto [v, weight] : graph[u]) {
  44.             if (dist[u] + weight < dist[v]) {
  45.                 dist[v] = dist[u] + weight;
  46.                 pq.push({dist[v], v});
  47.             }
  48.         }
  49.     }
  50.  
  51.     return dist;
  52. }
  53.  
  54. void solve() {
  55.     cin >> n >> m;
  56.     cin >> start >> destination;
  57.  
  58.     graph.resize(n + 1);
  59.     taxis.resize(n + 1);
  60.  
  61.     for (int i = 0; i < m; i++) {
  62.         int u, v;
  63.         ll w;
  64.         cin >> u >> v >> w;
  65.         graph[u].push_back({v, w});
  66.         graph[v].push_back({u, w});
  67.     }
  68.  
  69.     for (int i = 1; i <= n; i++) {
  70.         cin >> taxis[i].maxDistance >> taxis[i].cost;
  71.     }
  72.  
  73.     vector<vector<ll>> shortestPaths(n + 1, vector<ll>(n + 1, OO));
  74.  
  75.     for (int i = 1; i <= n; i++) {
  76.         shortestPaths[i] = dijkstra(i);
  77.     }
  78.  
  79.     vector<vector<Edge>> taxiGraph(n + 1);
  80.  
  81.     for (int i = 1; i <= n; i++) {
  82.         for (int j = 1; j <= n; j++) {
  83.             if (i != j && shortestPaths[i][j] <= taxis[i].maxDistance) {
  84.                 taxiGraph[i].push_back({j, taxis[i].cost});
  85.             }
  86.         }
  87.     }
  88.  
  89.     vector<ll> minCost(n + 1, OO);
  90.     priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq;
  91.  
  92.     minCost[start] = 0;
  93.     pq.push({0, start});
  94.  
  95.     while (!pq.empty()) {
  96.         auto [currCost, u] = pq.top();
  97.         pq.pop();
  98.  
  99.         if (currCost > minCost[u]) continue;
  100.  
  101.         for (auto [v, cost] : taxiGraph[u]) {
  102.             if (minCost[u] + cost < minCost[v]) {
  103.                 minCost[v] = minCost[u] + cost;
  104.                 pq.push({minCost[v], v});
  105.             }
  106.         }
  107.     }
  108.  
  109.     cout << (minCost[destination] == OO ? -1 : minCost[destination]) << endl;
  110. }
  111.  
  112. int main() {
  113.     EGRY
  114.     ll t = 1;
  115.     // cin >> t;
  116.  
  117.     while (t--) {
  118.         solve();
  119.     }
  120.  
  121.     return 0;
  122. }
  123.  
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/xpiI7A
language:
C++14 (gcc 8.3)
created:
9 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!