fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. using namespace std;
  4.  
  5. const int N = 1e5+1;
  6. vector<pair<int,int>> g[N];
  7. bool vis[N];
  8. int n,m,Time,Result,S[N],T[N];
  9.  
  10. void Topo(int s)
  11. {
  12.     for(auto x : g[s])
  13.         if(!T[x.first]) Topo(x.first);
  14.         T[Time--]=s;
  15. }
  16.  
  17. void DFS(int u)
  18. {
  19.     vis[u] = true;
  20.     for(auto x : g[u])
  21.     {
  22.         int v = x.first;
  23.         int w = x.second;
  24.         if(!vis[v]) DFS(v);
  25.         S[u] = max(S[v] + w,S[u]);
  26.     }
  27. }
  28.  
  29. signed main()
  30. {
  31.     freopen("MAXPDAG.INP","r",stdin);
  32.     freopen("MAXPDAG.out","w",stdout);
  33.     ios_base::sync_with_stdio(0);
  34.     cin.tie(0);
  35.     cin >> n >> m;
  36.     Time = n;
  37.     for(int i = 1; i <= m; ++i)
  38.     {
  39.         int x,y,w;
  40.         cin >> x >> y >> w;
  41.         g[x].push_back({y,w});
  42.     }
  43.  
  44.     for(int i = 1; i <= n; i ++)
  45.         if(!vis[i]) Topo(i);
  46.  
  47.     for(int i = 1; i <= n; i++)
  48.         if(!vis[T[i]]) DFS(T[i]);
  49.  
  50.     for(int i = 1; i <= n; i++)
  51.         Result = max(Result,S[i]);
  52.  
  53.     cout << Result;
  54. }
  55.  
Success #stdin #stdout 0.01s 7208KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/5LmaJd
Longest Routes _ Topo sort, DFS
language:
C++14 (gcc 8.3)
created:
13 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!