Description
Diao Biao received a task for the tax department to investigate the accounts of a businessman to see if the accounts were forged. The book records income over the past n months, of which the income for the first month is Ai (i = 1,2,3…n-1,n). When Ai is greater than 0, this month is full.Li Ai yuan, when Ai is less than 0, that this month loss Ai yuan. The total income in a period of time is the sum of the monthly income in this period. Diao Biao’s task was carried out in secret. In order to investigate the account books of the businessmen, she had to go to the businessmen to work. She stole while the merchant was away.Looking at the books, she couldn’t steal them out. Every time she peeked at the books, she could only look at the income recorded in the books for a certain period of time, and she could only remember the total income during that period. Now, Diao Jia peeked at the account book M times altogether, of course, also remembered the total income of m period of time, your task is rootAccording to these information, can we judge whether the account is false?
Input
The first behavior is a positive integer w, where W & lt; 100, indicating that there is a group of W data, that is, w accounts, you need to judge. The first behavior of each set of data is two positive integers n and m, where n< 100, m< 1000, respectively, denote the number of corresponding books recorded.Less than a month’s income and how many times the accounts have been peeped. The next M lines represent the M pieces of information that Diao Biao remembered after peeking at the m times of the book. Each line contains three integers, s, t, and v, indicating that the total income from month s to month t (including month t) is v, assuming that s is always less than equalAt t.
Output
Contains w rows, each of which is true or false, where the first action is true if and only if the data in group i, i.e. the first account is not false; the second action is false if and only if the data in group i, i.e. the second account is false.
Sample Input
3 3
1 2 10
1 3 -5
3 3 -15
5 3
1 5 100
3 5 50
1 2 51
Sample Output
false
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
#define reg register
inline int read() {
int res=0;char ch=getchar();bool fu=0;
while(!isdigit(ch)) {if(ch=='-')fu=1;ch=getchar();}
while(isdigit(ch))res=(res<<3)+(res<<1)+(ch^48),ch=getchar();
return fu?-res:res;
}
#define N 105
#define M 6005
int T;
int n, m;
struct edge {
int nxt, to, val;
}ed[M];
int head[M], cnt;
inline void add(int x, int y, int z) {
ed[++cnt] = (edge){head[x], y, z};
head[x] = cnt;
}
int tim[M];
int S;
int dis[M];
bool ex[M];
inline bool spfa()
{
memset(dis, 0x3f, sizeof dis);
dis[S] = 0;
queue <int> q;
q.push(S);
while(!q.empty())
{
int x = q.front();q.pop();
tim[x]++;
if (tim[x] >= n) return 0;
ex[x] = 0;
for (reg int i = head[x] ; i ; i = ed[i].nxt)
{
int to = ed[i].to;
if (dis[to] > dis[x] + ed[i].val)
{
dis[to] = dis[x] + ed[i].val;
if (!ex[to]) ex[to] = 1, q.push(to);
}
}
}
return 1;
}
int main()
{
T = read();
while(T--)
{
memset(head, 0, sizeof head);
memset(tim, 0, sizeof tim);
memset(ex, 0, sizeof ex);
cnt = 0;
n = read(), m = read();
S = n + 1;
for (reg int i = 0 ; i <= n ; i ++)
add(S, i, 0);
for (reg int i = 1 ; i <= m ; i ++)
{
int x = read(), y = read(), z = read();
add(x - 1, y, z), add(y, x - 1, -z);
}
if (spfa()) puts("true");
else puts("false");
}
return 0;
}