[POJ] 1201 - Intervals

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 1201 - Intervals
Source            : POJ
Category          : Graph Theory
Algorithm         : System of Difference Constraints
Verdict           : Accepted

#include <iostream>  
#include <vector>  
#include <queue>  
  
using namespace std;  
  
static const int maxn = 50000 + 5;  
static const int inf  = 1e6+9;  
  
struct edge  
{  
      int u, v, w;  
      edge(int uu = 0, int vv = 0, int ww = 0) : u(uu), v(vv), w(ww) {}  
};  
  
struct node  
{  
    int v, w;  
    node(int vv = 0, int ww = 0) : v(vv), w(ww) {}  
};  
  
vector <edge> edgeList;  
vector <node> graph[maxn];  
int tinterval;  
int dis[maxn], now[maxn], cnt[maxn];  
  
inline void spfa(int src = 0)  
{  
      for (int i = 0; i < maxn; i++)  
      {  
            dis[i] = inf;  
            now[i] = 0;  
            cnt[i] = 0;  
      }  
      queue <int> PQ;  
      PQ.push(src);  
      dis[src] = 0;  
      cnt[src] = 1;  
      now[src] = 1;  
      while (!PQ.empty())  
      {  
            int u = PQ.front(); PQ.pop();  
            now[u] = 0;  
            //if (cnt[u] > tinterval)  // negative cycle found  
            //    return false;  
            for (vector <node>::iterator it = G[u].begin(); it != G[u].end(); it++)  
            {  
                  int v = it->v;  
                  int w = it->w;  
                  if (dis[v] > dis[u] + w)  
                  {  
                  dis[v] = dis[u] + w;  
                  //cnt[v]++;  
                  if (!now[v]) PQ.push(v), now[v] = 1;  
                  }  
            }  
      }  
}  
  
inline void createGraph(int maxi)  
{  
      for (vector<edge>::iterator it = E.begin(); it != E.end(); it++)  
      {  
            int u = it->u, v = it->v, w = it->w;  
            graph[v].push_back(node(u, -w));  
      }  
      for (int i = 1; i < maxi; i++)  
      {  
            G[i].push_back(node(i+1, 1));  
            G[i+1].push_back(node(i, 0));  
      }  
      for (int i = 1; i <= maxi; i++)  
      {  
            G[0].push_back(node(i, 0));  
      }  
}  
  
int main()  
{  
      //freopen("in.txt", "r", stdin);  
  
      scanf("%d", &tinterval);  
      int maxi = -1;  
      int mini = inf;  
      for (int i = 0; i < tinterval; i++)  
      {  
            int u, v, w;  
            scanf("%d %d %d", &u, &v, &w);  
            u += 1;  
            v += 2;  
            edgeList.push_back(edge(u, v, w));  
            maxi = max(maxi, max(u, v));  
            mini = min(mini, min(u, v));  
      }  
      createGraph(maxi);  
      spfa();  
      printf("%d\n", -dis[mini]);  
}