区间和(图论）

小明与小红在玩一个猜谜游戏。小红有一个长度为N的下标从1开始的数组A。起初时，小明并不知道数组里的任何数。但是小红会告诉小明Q个关于数组A的信息，每个信息包括三个数字L、R、W表示：
A[L] + A[L + 1] + ... + A[R] = W

现在小红要小明用这Q组信息来推出数组A的值，小明希望你能够帮助他。

输入格式:

第一行输入两个正整数N(1≤N≤2000)、Q(1≤Q≤3000)

接下来Q行，每行3个正整数，分别是L、R、W(1≤L,R≤N)

数据保证所有的W加起来不会超过int的最大范围。

输出格式:

若这Q组信息不矛盾，那么输出一行，共N个数。第i个数表示数组A[i]的值，如果无法推测出A[i]的值，那么用字母o代替

若这Q组信息出现矛盾，那么输出一个字符x即可

输入样例1:

4 3
1 3 2
2 3 1
1 2 5

输出样例1:

1 4 -3 o

题目给出了信息：A[1]+A[2]+A[3]=2、A[2]+A[3]=1、A[1]+A[2]=5

A[4]无法根据已知信息推导出来

A[1]=A[1]+A[2]+A[3]−(A[2]+A[3])=2−1=1

A[2]=A[1]+A[2]−A[1]=5−1=4

A[3]=A[2]+A[3]−A[2]=1−4=−3

输入样例2:

4 3
3 3 2
1 2 2
1 3 3

输出样例2:

x

题目给出了A[3]=2， 又有A[3]=A[3]+A[2]+A[1]−(A[1]+A[2])=3−2=1, 产生矛盾，因此只输出一个字符x

把和抽象成图 建边 

a[1]+a[2]+a[3]=2---> 0到3距离为2 

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int N=2200;
int g[N][N];
int dist[N];//虚拟原点0 dist[]数组表示0-其他点的距离
int n,m;
int flag;
void bfs()
{
	memset(dist,0x3f,sizeof dist);
	dist[0]=0;
	queue<int>q;
	q.push(0);
	while(q.size())
	{
		int t=q.front();
		q.pop();
		for(int i=0;i<=n;i++)
		{
			if(g[t][i]!=0x3f3f3f3f)
			{
				if(dist[i]==0x3f3f3f3f)
				{
					dist[i]=dist[t]+g[t][i];
					q.push(i);
				}
				else if(dist[i]!=dist[t]+g[t][i])
				{
					flag=1;
					break;
				}
			}
		}
	}
}
int main()
{
	cin>>n>>m;
	memset(g,0x3f,sizeof g);
	while(m--)
	{
		int a,b,c;cin>>a>>b>>c;
		g[a-1][b]=c;
		g[b][a-1]=-c;
	}
	bfs();
	if(flag) cout<<"x"<<endl;
	else
	{
		int tt=0;
		for(int i=1;i<=n;i++)
		{
			if(tt)cout<<" ";
			if(dist[i]==0x3f3f3f3f||dist[i-1]==0x3f3f3f3f) cout<<"o";
			else cout<<dist[i]-dist[i-1];
			tt=1;
		}
	}
	return 0;
}