Bellman-Ford的思路,只输出-2,新人求调
查看原帖
Bellman-Ford的思路,只输出-2,新人求调
1054807
TomRiddle楼主2024/7/28 16:15
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll N = 1e4 + 1;
ll n, ml, mr, a, b, d, dis[N];
vector<pair<ll, ll>> bian[N];
int main()
{
	cin>>n>>ml>>mr;
	for (int i = 2;i <= n;i++) dis[i] = 1e12;
	for (int i = 1;i <= ml;i++)
	{
		cin>>a>>b>>d;
		bian[b].push_back(make_pair(d, a));
	}
	for (int i = 1;i <= mr;i++)
	{
		cin>>a>>b>>d;
		bian[b].push_back(make_pair(-d, a));
	}
	for (int j = 1;j <= n;j++)
	{
		for (int i = 1;i <= n;i++)
		{
			for (auto k : bian[i]) dis[k.second] = min(dis[k.second], dis[i] + k.first);
		}
	}
	for (int i = 1;i <= n;i++)
	{
		for (auto k : bian[i])
		{
			if (dis[k.second] > dis[i] + k.first)
			{
				cout<<-1;
				return 0;
			}
		}
	}
	if (dis[n] == 1e12)
	{
		cout<<-2;
		return 0;
	}
	else cout<<dis[n];
}
2024/7/28 16:15
加载中...