Advertisement
Guest User

Untitled

a guest
Mar 21st, 2019
64
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.80 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define PI 2*asin(1)
  3. #define FOR(i,n) for(long long i = 0; i < n;i++)
  4. using namespace std;
  5. long long n,m,s,t;
  6. vector<vector<long long>>ch(100001);
  7. vector <long long>res;
  8. vector<vector<long long>>rast(100001);
  9. void go(long long v){
  10.     for(long long i : rast[v]){
  11.         res[i] = min(res[i], res[v]+ch[v][i]);
  12.         go(i);
  13.     }
  14. }
  15. int main()
  16. {
  17.     ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  18.  
  19.     cin >> n >> m >> s >> t; s--;t--;
  20.     FOR(i,n) res.push_back(INT_MAX);
  21.     FOR(i,n) FOR(j,m) ch[i].push_back(0);
  22.     res[s] = 0;
  23.     FOR(i,m){
  24.         long long x,y,z;cin >> x >> y >> z; x--;y--;
  25.         rast[x].push_back(y);
  26.         ch[x][y] = z;
  27.     }
  28.     go(s);
  29.     long long y = res[t];
  30.     if(y<INT_MAX)cout << res[t];
  31.     else cout << "Unreachable";
  32. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement