Advertisement
Emiliatan

e158

May 4th, 2019
184
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.14 KB | None | 0 0
  1. /* e158           */
  2. /* AC (61ms, 3MB) */
  3. #include <cstdio>
  4. #include <queue>
  5. #include <vector>
  6.  
  7. using namespace std;
  8.  
  9. const int maxn = 50005 , INF = 1e9;
  10.  
  11. struct Edge{
  12.     int to , w;
  13. };
  14.  
  15. vector <Edge> g[maxn];
  16. int cur = 0 , n , a , b , c , max0 = 0;
  17. int d[maxn];
  18. bool in[maxn];
  19.  
  20. int spfa(int s , int t) {
  21.     queue <int> q;
  22.     fill(in, in + max0 + 1, 0);
  23.     fill(d, d + max0 + 1, INF);
  24.     d[s] = 0; q.push(s);
  25.     while(q.size()) {
  26.         int now = q.front(); q.pop(); in[now] = 0;
  27.         for(int i = 0, l = g[now].size(); i < l; ++i) {
  28.             int nex = g[now][i].to;
  29.             if(d[nex] == INF || d[nex] < d[now] + g[now][i].w) {
  30.                 d[nex] = d[now] + g[now][i].w;
  31.                 if(!in[nex]) in[nex] = 1 , q.push(nex);
  32.             }
  33.         }
  34.     }
  35.     return d[t];
  36. }
  37.  
  38. int main() {
  39.     scanf("%d", &n);
  40.     for(int i = 1; i <= n; ++i) {
  41.         scanf("%d %d %d", &a, &b, &c);
  42.         g[a - 1].push_back({b, c});
  43.         max0 = max(max0, b);
  44.     }
  45.     for(int i = 0; i < max0; ++i) g[i].push_back({i + 1, 0}), g[i + 1].push_back({i, -1});
  46.     printf("%d\n",spfa(0, max0));
  47.  
  48.     return 0;
  49. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement