POJ 3169 Layout

#include <stdio.h>
#include <string.h>
#include <assert.h>

#include <vector>
#include <queue>

using namespace std;

struct Edge
{
  int cost;
  int target;

  Edge(int targetI = 0, int costI = 0): target(targetI), cost(costI) {};
};

vector<vector<Edge> > G;
queue<int> q;
const int MAXN = 10000 + 5;
bool inq[MAXN];
int inqCnt[MAXN];
long long dis[MAXN];
const long long INF = 0x7f7f7f7f7f7f7f7f;

long long bellmanFord(int  n)
{
  memset(inq, 0, sizeof(bool) * (n + 1));
  memset(inqCnt, 0, sizeof(int) * (n + 1));
  memset(dis, 0x7f, sizeof(long long) * (n + 1));
  assert(INF == dis[0]);
  dis[1] = 0;
  q.push(1);
  inq[1] = true;
  inqCnt[1] = 1;
  for (; !q.empty(); ) {
    int u = q.front();
    q.pop();
    inq[u] = false;
    for (int i = 0; i < G[u].size(); i++) {
      int v = G[u][i].target;
      int cost = G[u][i].cost;
      if (dis[v] > dis[u] + cost) {
        dis[v] = dis[u] + cost;
        if (!inq[v]) {
          q.push(v);
          inqCnt[v]++;
          inq[v] = true;
          if (inqCnt[v] == n)
            return -1;
        }
      }
    }
  }
  if (dis[n] == INF)
    return -2;
  return dis[n];
}

int main()
{
  int n, ml, md;
  scanf("%d %d %d", &n, &ml, &md);
  G.resize(n + 1);

  int u, v, d;
  for (int i = 0; i < ml; i++) {
    scanf("%d %d %d", &u, &v, &d);
    // s[v] - s[u] <= d
    G[u].push_back(Edge(v, d));
  }
  for (int i = 0; i < md; i++) {
    scanf("%d %d %d", &u, &v, &d);
    // s[v] - s[u] >= d
    // s[u] - s[v] <= -d
    G[v].push_back(Edge(u, -d));
  }
  // s[i] - s[i+1] <= 0
  for (int i = 1; i < n; i++)
    G[i+1].push_back(Edge(i, 0));

  printf("%I64d\n", bellmanFord(n));
  return 0;
}
/*
4 2 1
1 3 10
2 4 20
2 3 3
*/