Advertisement
Zuneve

фцв

Sep 22nd, 2023
755
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.10 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. using ll = long long;
  6.  
  7. const ll INF = 1e15 + 7;
  8.  
  9. vector<ll> used;
  10. vector<ll> topsort;
  11.  
  12. void dfs_ts(ll v, vector<map<ll, ll>> &gr) {
  13.     used[v] = true;
  14.     for (auto [u, k] : gr[v]) {
  15.         if (!used[u]) {
  16.             dfs_ts(u, gr);
  17.         }
  18.     }
  19.     topsort.push_back(v);
  20. }
  21.  
  22. int main() {
  23.     ll n, m, s, t;
  24.     cin >> n >> m >> s >> t;
  25.     --s;
  26.     --t;
  27.     vector<map<ll, ll>> gr(n);
  28.     for (ll i = 0; i < m; i++) {
  29.         ll a, b, c;
  30.         cin >> a >> b >> c;
  31.         --a;
  32.         --b;
  33.         gr[a][b] = c;
  34.     }
  35.     used.assign(n, false);
  36.     for (ll i = 0; i < n; i++) {
  37.         if (!used[i]) dfs_ts(i, gr);
  38.     }
  39.     reverse(topsort.begin(), topsort.end());
  40.     vector<ll> dp(n, INF);
  41.     dp[s] = 0;
  42.     for (ll i = 0; i < n; i++) {
  43.         if (dp[i] < INF) {
  44.             for (auto [u, k] : gr[topsort[i]]) {
  45.                 dp[u] = min(dp[u], dp[topsort[i]] + k);
  46.             }
  47.         }
  48.     }
  49.     if (dp[t] == INF) {
  50.         cout << "Unreachable";
  51.     } else {
  52.         cout << dp[t];
  53.     }
  54.     return 0;
  55. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement