Advertisement
Zuneve

awd

Sep 22nd, 2023
860
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.25 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.     ll i;
  41.     for (i = 0; i < n; i++) {
  42.         if (topsort[i] == s) {
  43.             break;
  44.         }
  45.     } ll S = i;
  46.     vector<ll> dp(n, INF);
  47.     used.assign(n, false);
  48.     dp[s] = 0;
  49.     for (i = S; i < n; i++) {
  50.         if (dp[topsort[i]] != INF) {
  51.             for (auto [u, k] : gr[topsort[i]]) {
  52.                 dp[u] = min(dp[u], dp[topsort[i]] + k);
  53.             }
  54.         }
  55.     }
  56.     if (dp[t] == INF) {
  57.         cout << "Unreachable";
  58.     } else {
  59.         cout << dp[t];
  60.     }
  61.     return 0;
  62. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement