fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define el '\n'
  4. #define oo LLONG_MAX >> 2
  5. #define all(x) x.begin(), x.end()
  6. #define allr(x) x.rbegin(), x.rend()
  7. #define pb push_back
  8. #define pep_Guardiola                                                          \
  9.   ios::sync_with_stdio(0);                                                     \
  10.   cin.tie(0);                                                                  \
  11.   cout.tie(0);
  12. using namespace std;
  13. struct Node {
  14.   int u;
  15.   ll cost;
  16.   int mn, mx;
  17.   Node() = default;
  18.   Node(int u, ll cost, int mn, int mx) : u(u), cost(cost), mn(mn), mx(mx) {}
  19.   bool operator<(const Node &other) const { return cost > other.cost; }
  20. };
  21. signed main() {
  22.   pep_Guardiola int n, m, s, x;
  23.   cin >> n >> m >> s >> x;
  24.   s--;
  25.   vector<vector<pair<int, int>>> adj(n);
  26.   for (int i = 0, u, v, w; i < m; i++)
  27.     cin >> u >> v >> w, u--, v--, adj[u].push_back({v, w}),
  28.         adj[v].push_back({u, w});
  29.   ll dist[n][2][2];
  30.   for (int i = 0; i < n; i++)
  31.     for (int j = 0; j < 2; j++)
  32.       for (int z = 0; z < 2; z++)
  33.         dist[i][j][z] = oo;
  34.   dist[s][0][0] = 0;
  35.   priority_queue<Node> pq;
  36.   pq.push({s, 0, 0, 0});
  37.   while (pq.size()) {
  38.     auto [u, cost, mn, mx] = pq.top();
  39.     pq.pop();
  40.     if (dist[u][mn][mx] < cost)
  41.       continue;
  42.     for (auto &[v, w] : adj[u]) {
  43.       if (dist[v][mn][mx] > cost + w + x)
  44.         pq.push({v, dist[v][mn][mx] = cost + w + x, mn, mx});
  45.       if (!mn && dist[v][1][mx] > cost + 2 * w + x)
  46.         pq.push({v, dist[v][1][mx] = cost + 2 * w + x, 1, mx});
  47.       if (!mx && dist[v][mn][1] > cost + x)
  48.         pq.push({v, dist[v][mn][1] = cost + x, mn, 1});
  49.       if (!mx && !mn && dist[v][1][1] > cost + x + w)
  50.         pq.push({v, dist[v][1][1] = cost + w + x, 1, 1});
  51.     }
  52.   }
  53.   for (int i = 0; i < n; i++)
  54.     if (i != s)
  55.       cout << dist[i][1][1] << ' ';
  56. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
4 5 1 25
1 2 69
2 3 10
3 4 68
4 1 17
1 3 35
stdout
copy 
70 60 42
https://ideone.com/G5T0bS
language:
C++ (gcc 8.3)
created:
1 day 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!