Submission #3453217

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
const int N=1e5*2+10;
inline int read()
{
	char ch=getchar();
	int x=0,f=1;
	while (ch>'9' || ch<'0')
	{
		if (ch=='-') f=-1;
		ch=getchar();
	}
	while (ch>='0' && ch<='9')
	{
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*f;
}
int i,j,k,t,m,n,mind,maxd;
int dis[N<<1];
bool vis[N<<1];
struct EDGE
{
	int nex,to,w;
} edge[N<<1];
int head[N<<1],cnt,ans;
inline void add(int x,int y,int z)
{
	edge[++cnt].to=y;
	edge[cnt].nex=head[x];
	head[x]=cnt;
	edge[cnt].w=z;
}
int fail=0;
inline bool dfs(int u)
{
	vis[u]=1;
	for (int i=head[u];i;i=edge[i].nex)
	{
		int v=edge[i].to,w=edge[i].w;
		if (vis[v])
		{
			if (dis[u]+w!=dis[v]) return false;			
		}
		else
		{
			dis[v]=dis[u]+w;
			maxd=max(maxd,dis[v]);
			mind=min(mind,dis[v]);
			if (!dfs(v)) return false;
		}
	}
	return true;
}
int main()
{
	n=read();m=read();
	for (int i=1;i<=m;i++)
	{
		int x=read(),y=read(),z=read();
		add(x,y,z);
		add(y,x,-z);
	}
	for (int i=1;i<=n;i++)
	{
		if (!vis[i])
		{
			dis[i]=0;
			maxd=0;
			mind=0;
			if (!dfs(i))
			{
				fail=1;
				break;
			}
			ans=max(ans,maxd-mind);
		}
	}
	if (fail)
	{
		printf("impossible");
		return 0;
	}
	else printf("%d\n",ans);
	return 0;
}

Submission Info

Judge Result