1s 128M

题目描述 阿福最近沉迷炒股，然而作为韭菜，阿福总是每天在赚钱和亏钱之间挣扎。一共有n天，每天阿福可以视为通过炒股赚了ai元。ai经常是负的，表示阿福炒股在这一天亏钱了。

阿福的老婆阿翠不希望阿福花太多钱在炒股上，于是旁敲侧击地询问阿福炒股的盈亏，得到了m条这样的信息：阿福炒股的第l天到第r天总共通过炒股赚了x元（x可以是负的）。

然而阿翠还是满腹疑虑，担心阿福为了哄她说假话。她想判断一下阿福告诉他的这些信息是否自相矛盾。

输入格式 第一行为一个正整数 T表示数据组数。

每组数据的第一行为两个正整数 n 和 m，含义如题目描述所述。

接下来的 m 行表示 m 条信息，每条信息占一行，有三个整数 l, r, x ，含义如题目描述所述。

输出格式 包含 T 行，每行是 true 或 false，其中第 i 行为 true 当且仅当第 i 组数据不自相矛盾；第 i 行为 false 当且仅当第 i 组数据自相矛盾。

样例 #1 样例输入 #1 2

3 3

1 2 10

1 3 -5

3 3 -15

5 3

1 5 100

3 5 50

1 2 51

样例输出 #1

true

false

数据范围

T ≤ 100, n ≤ 100, m ≤ 1000, 1 ≤ l ≤ r ≤ n,  − 1012 ≤ x ≤ 1012

#include<bits/stdc++.h>
#define F( i , a , b ) for( register int i = ( a ) ; i <= ( b ) ; ++ i )
#define int long long
using namespace std;
const int N=150;
int dis[N],sum[N],n,m;
int vis[N];
vector<int>g[N],w[N];
inline int read(){register int x=0,f=1;register char ch=getchar();while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}while (ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
void add(int u,int v,int W)
{
	g[u].push_back(v);
	w[u].push_back(W);
}
bool check(int rt)
{
	queue<int>q;
	memset(dis,0x3f,sizeof(dis));
	memset(sum,0,sizeof(sum));
	dis[rt]=0;
	q.push(rt);
	while(q.size())
	{
		int u=q.front();
		q.pop();
		sum[u]++;
		if(sum[u]>n)
		{
			return 0;
		}
		for(register int i = 0;i<g[u].size();i++)
		{
			int v=g[u][i];
			if(dis[v]>dis[u]+w[u][i])
			{
				dis[v]=dis[u]+w[u][i];
				q.push(v);
			}
		}
	}
	return 1;
}
inline void solve()
{
	n=read(),m=read();
	F(i,1,m)
	{
		int l=read(),r=read(),x=read();
		//x_r-x_(l-1)>=0  <=0
		add(r,l-1,x);
		add(l-1,r,-x); 
	//	cout <<"#"<< r << " " << l-1 <<" " <<x << "\n";
	//	cout <<"#"<< l-1 << " " << r <<" " <<-x << "\n";
		vis[l-1]=1;
		vis[r]=1;
	}
	memset(dis,0x3f,sizeof(dis));
	for(int i = 0;i<=n;i++)
	{
		if(vis[i])
		{
		//	cout << i << "\n";
			if(!check(i))
			{
				puts("false");
				return;
			}
		}
	}
	puts("true");
	return;
}
/*
1
5 3
1 5 100
3 5 50
1 2 51
*/
int main()
{
	int T=read();
	while(T--)
	{
		solve();
	}
	return 0;
}

结果：T+WA 10pts