# Instrction Arrangement

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 1395    Accepted Submission(s): 584

Problem Description

Ali has taken the Computer Organization and Architecture course this term. He learned that there may be dependence between instructions, like WAR (write after read), WAW, RAW.

If the distance between two instructions is less than the Safe Distance, it will result in hazard, which may cause wrong result. So we need to design special circuit to eliminate hazard. However the most simple way to solve this problem is to add bubbles (useless
operation), which means wasting time to ensure that the distance between two instructions is not smaller than the Safe Distance.

The definition of the distance between two instructions is the difference between their beginning times.

Now we have many instructions, and we know the dependent relations and Safe Distances between instructions. We also have a very strong CPU with infinite number of cores, so you can run as many instructions as you want simultaneity, and the CPU is so fast that
it just cost 1ns to finish any instruction.

Your job is to rearrange the instructions so that the CPU can finish all the instructions using minimum time.

Input

The input consists several testcases.

The first line has two integers N, M (N <= 1000, M <= 10000), means that there are N instructions and M dependent relations.

The following M lines, each contains three integers X, Y , Z, means the Safe Distance between X and Y is Z, and Y should run after X. The instructions are numbered from 0 to N - 1.

Output

Print one integer, the minimum time the CPU needs to run.

Sample Input

```5 2
1 2 1
3 4 1
```

Sample Output

```2

Hint

In the 1st ns, instruction 0, 1 and 3 are executed;
In the 2nd ns, instruction 2 and 4 are executed.
So the answer should be 2.
```

Source

2011 Alibaba-Cup Campus Contest

Recommend

lcy   |   We have carefully selected several similar problems for you:  4103 4105 4104 4101 4102

```#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<string>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
using namespace std;
#define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define REP( i , n ) for ( int i = 0 ; i < n ; ++ i )
#define CLEAR( a , x ) memset ( a , x , sizeof a )
const int INF=0x3f3f3f3f;
typedef long long LL;

const int MAXM = 100000;
const int MAXN = 1005;

struct Edge
{
int u,v,len,next;
}edge[MAXM];

int n,m,num;

void init()
{
num=0;
}

void addedge(int u,int v,int len)
{
edge[num].u=u;
edge[num].v=v;
edge[num].len=len;
}

void spfa()
{
memset(dist,INF,sizeof(dist));
memset(inq,0,sizeof(inq));
inq[0]=1;
dist[0]=0;
queue<int>Q;
Q.push(0);
while (!Q.empty())
{
int u=Q.front();
Q.pop();
inq[u]=0;
{
int v=edge[i].v;
if (dist[v]>dist[u]+edge[i].len)
{
dist[v]=dist[u]+edge[i].len;
if (!inq[v])
{
inq[v]=1;
Q.push(v);
}
}
}
}
printf("%d\n",-dist[n+1]);
}

int main()
{
int i,j,u,v,w;
while (~scanf("%d%d",&n,&m))
{
init();
for (i=0;i<m;i++)
{
scanf("%d%d%d",&u,&v,&w);
u++,v++;
}
for (i=1;i<=n;i++)
{
}
spfa();
}
return 0;
}
```

## hdu 1364(差分约束)

King Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 12056   Accepted: 4397 Description Once, in one kingdom, there was a queen and that queen was expecting a baby. The queen prayed: ``If my child was a son and if only he was a sound kin

## poj2983——差分约束，bellman_ford

poj2983——差分约束,bellman_ford Is the Information Reliable? Time Limit: 3000MS   Memory Limit: 131072K Total Submissions: 11560   Accepted: 3658 Description The galaxy war between the Empire Draco and the Commonwealth of Zibu broke out 3 years ago. Draco

## 差分约束

1.bzoj3436 思路: 差分约束根据限制条件建图,注意要有一个超级源点向所有点连一条边权为0的边建图看代码. 然后spfa判负环,写bfs会超时的......实测n遍. #include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #define inf 0x7fffffff #define ll long long #define N 100007 using na

## POJ 1201 Intervals 差分约束

http://poj.org/problem?id=1201 TLE了很久,因为用了cin..... 思路和其他差分约束差不多,http://www.cppblog.com/menjitianya/archive/2015/11/19/212292.html 如果区间[a, b]中至少有c个元素,如果用上面的博客,那么说明xa - xb >= c,但是注意这里是闭区间,xa - xb是不包括b这个点的, 就比如用了[a, b]有c个元素,[b, d]有x个,那么ans = c + x - 1个,

## 【bzoj2330】: [SCOI2011]糖果 图论-差分约束-SPFA

[bzoj2330]: [SCOI2011]糖果 恩..就是裸的差分约束.. x=1 -> (A,B,0) (B,A,0) x=2 -> (A,B,1)  [这个情况加个A==B无解的要特判] x=3 -> (B,A,0)  [恩这个是不少于一开始zz建反了] x=4 -> (B,A,1) x=5 -> (A,B,0) 然后源点到所有点建1的边[恩据说有条链所以要反着连]跑最长路就好了 1 /* http://www.cnblogs.com/karl07/ */ 2 #inc