SHARE
TWEET

Untitled

a guest Jul 23rd, 2019 54 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. vector<bool> u;
  6. vector<vector<pair<int, int>>> g;
  7. void dfs(int v){
  8.     u[v] = true;
  9.     for (pair<int, int>&p : g[v]){
  10.         if (!u[p.first])
  11.             dfs(p.first);
  12.     }
  13. }
  14.  
  15.  
  16. int main() {
  17.     const int INF = 1e9;
  18.     int n, m;
  19.     cin >> n >> m;
  20.     g.resize(n); u.resize(n);
  21.     int f, t, w;
  22.     for (int i = 0; i < m; ++i) {
  23.         cin >> f >> t >> w;
  24.         f--;
  25.         t--;
  26.         g[f].push_back({t, w});
  27.     }
  28.     vector<int> d(n, -INF);
  29.     vector<int> tmp;
  30.     d[0] = 0;
  31.     for (int k = 0; k < n; ++k) {
  32.         for (int i = 0; i <n ;++i){
  33.             for (pair<int, int> &p : g[i]){
  34.                 if (d[i] != -INF && d[p.first] < d[i] + p.second){
  35.                     d[p.first] = d[i] + p.second;
  36.                     if (k == n-1)
  37.                         tmp.push_back(p.first);
  38.                 }
  39.             }
  40.         }
  41.     }
  42.     for (int i = 0; i < tmp.size(); ++i)
  43.         dfs(tmp[i]);
  44.     if (u[n-1]) cout << ":)";
  45.     else if (d[n-1] == -INF) cout << ":(";
  46.     else cout << d[n-1];
  47.     return 0;
  48. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top