fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. vector<int> getMinimumLength(int roads_nodes, vector<int> roads_from, vector<int> roads_to, vector<int> roads_weight) {
  5.     const int n = roads_nodes;
  6.     const int m = (int)roads_from.size();
  7.  
  8.     vector<vector<pair<int,int>>> adj(n + 1), rev(n + 1);
  9.     for (int i = 0; i < m; ++i) {
  10.         adj[roads_from[i]].push_back({roads_to[i], roads_weight[i]});
  11.         rev[roads_to[i]].push_back({roads_from[i], roads_weight[i]});
  12.     }
  13.  
  14.     const long long INF = LLONG_MAX;
  15.     vector<long long> dist(n + 1);
  16.     vector<int> result(n, 0);
  17.     using P = pair<long long, int>;
  18.  
  19.     for (int x = 1; x <= n; ++x) {
  20.         fill(dist.begin(), dist.end(), INF);
  21.         dist[x] = 0;
  22.  
  23.         priority_queue<P, vector<P>, greater<P>> pq;
  24.         pq.push({0, x});
  25.  
  26.         while (!pq.empty()) {
  27.             auto [d, u] = pq.top(); pq.pop();
  28.             if (d > dist[u]) continue;
  29.             for (auto [v, w] : adj[u]) {
  30.                 long long nd = d + w;
  31.                 if (nd < dist[v]) {
  32.                     dist[v] = nd;
  33.                     pq.push({nd, v});
  34.                 }
  35.             }
  36.         }
  37.  
  38.         long long best = INF;
  39.         for (auto [u, w] : rev[x]) {
  40.             if (dist[u] != INF) best = min(best, dist[u] + (long long)w);
  41.         }
  42.         result[x - 1] = (best == INF) ? 0 : (int)best;
  43.     }
  44.     return result;
  45. }
  46.  
  47. // ---------- Test harness ----------
  48. static void runTest(const string& name,
  49.                     int n,
  50.                     vector<int> from, vector<int> to, vector<int> w,
  51.                     vector<int> expected) {
  52.     vector<int> got = getMinimumLength(n, from, to, w);
  53.  
  54.     cout << name << "\n";
  55.     cout << "  Expected: [";
  56.     for (size_t i = 0; i < expected.size(); ++i)
  57.         cout << expected[i] << (i + 1 < expected.size() ? ", " : "");
  58.     cout << "]\n";
  59.  
  60.     cout << "  Got:      [";
  61.     for (size_t i = 0; i < got.size(); ++i)
  62.         cout << got[i] << (i + 1 < got.size() ? ", " : "");
  63.     cout << "]\n";
  64.  
  65.     cout << "  " << (got == expected ? "PASS" : "FAIL") << "\n\n";
  66. }
  67.  
  68. int main() {
  69.     // Problem-statement example: 4 nodes, edges 1->2:14, 2->3:23, 3->1:23, 4->3:30
  70.     runTest("Example (problem statement)",
  71.             4,
  72.             {1, 2, 3, 4},
  73.             {2, 3, 1, 3},
  74.             {14, 23, 23, 30},
  75.             {60, 60, 60, 0});
  76.  
  77.     // Sample Case 0: triangle 1->2->3->1, all weights 10
  78.     runTest("Sample Case 0",
  79.             3,
  80.             {1, 2, 3},
  81.             {2, 3, 1},
  82.             {10, 10, 10},
  83.             {30, 30, 30});
  84.  
  85.     // Sample Case 1: 4 nodes, 5 edges
  86.     // 1->3:20, 3->2:25, 2->1:15, 4->2:10, 1->4:5
  87.     runTest("Sample Case 1",
  88.             4,
  89.             {1, 3, 2, 4, 1},
  90.             {3, 2, 1, 2, 4},
  91.             {20, 25, 15, 10, 5},
  92.             {30, 30, 60, 30});
  93.  
  94.     return 0;
  95. }
Success #stdin #stdout 0s 5304KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Example (problem statement)
  Expected: [60, 60, 60, 0]
  Got:      [60, 60, 60, 0]
  PASS

Sample Case 0
  Expected: [30, 30, 30]
  Got:      [30, 30, 30]
  PASS

Sample Case 1
  Expected: [30, 30, 60, 30]
  Got:      [30, 30, 60, 30]
  PASS
https://ideone.com/vtzho1
language:
C++ (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!