Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- using ll = long long;
- const ll INF = 1e15 + 7;
- vector<ll> used;
- vector<ll> topsort;
- void dfs_ts(ll v, vector<map<ll, ll>> &gr) {
- used[v] = true;
- for (auto [u, k] : gr[v]) {
- if (!used[u]) {
- dfs_ts(u, gr);
- }
- }
- topsort.push_back(v);
- }
- int main() {
- ll n, m, s, t;
- cin >> n >> m >> s >> t;
- --s;
- --t;
- vector<map<ll, ll>> gr(n);
- for (ll i = 0; i < m; i++) {
- ll a, b, c;
- cin >> a >> b >> c;
- --a;
- --b;
- gr[a][b] = c;
- }
- used.assign(n, false);
- for (ll i = 0; i < n; i++) {
- if (!used[i]) dfs_ts(i, gr);
- }
- reverse(topsort.begin(), topsort.end());
- ll i;
- for (i = 0; i < n; i++) {
- if (topsort[i] == s) {
- break;
- }
- } ll S = i;
- vector<ll> dp(n, INF);
- used.assign(n, false);
- dp[s] = 0;
- for (i = S; i < n; i++) {
- if (dp[topsort[i]] != INF) {
- for (auto [u, k] : gr[topsort[i]]) {
- dp[u] = min(dp[u], dp[topsort[i]] + k);
- }
- }
- }
- if (dp[t] == INF) {
- cout << "Unreachable";
- } else {
- cout << dp[t];
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement