wa#13,求助
查看原帖
wa#13,求助
366746
烛木楼主2020/10/15 19:19
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#define int long long
#define MAXN 1000086
using namespace std;
int n,l,d,tot,minn=1e12,dis[MAXN],vis[MAXN],tim[MAXN];
struct node
{
	int first,next,go,value;
}p[MAXN];
queue<int>q;
inline void star(int a,int b,int c)
{
	p[++tot].next=p[a].first;
	p[a].first=tot;
	p[tot].go=b;
	p[tot].value=c;
}
inline int spfa(int a)
{
	dis[a]=0;
	q.push(a);
	++tim[a];
	while(!q.empty())
	{
		int x=q.front();
		q.pop();
		vis[x]=0;
		for(int i=p[x].first;i;i=p[i].next)
		{
			int y=p[i].go,z=p[i].value;
			if(dis[x]+z>dis[y])
			{
				dis[y]=dis[x]+z;
				if(!vis[y])
				{
					vis[y]=1;
					q.push(y);
					if(++tim[y]==n)
					{
						printf("-1");
						return 0;
					}
				}
			}
		}
	}
	return 1;
}
signed main()
{
	scanf("%lld %lld %lld",&n,&l,&d);
	for(int i=1;i<=n;i++) dis[i]=-1e12;
	for(int i=1;i<=l;i++)
	{
		int a,b,c;
		scanf("%lld %lld %lld",&a,&b,&c);
		star(a,b,-c);
		minn=min(minn,a);
	}
	for(int i=1;i<=d;i++)
	{
		int a,b,c;
		scanf("%lld %lld %lld",&a,&b,&c);
		star(b,a,c);
		minn=min(minn,b);
	}
	if(spfa(minn))
	{
		if(dis[n]==-1e12)
		{
			printf("-2");
			return 0;
		}
		else
		{
			printf("%lld",-dis[n]);
			return 0;
		}
	}
}
2020/10/15 19:19
加载中...