90pts#10WA
查看原帖
90pts#10WA
267125
宋小陀螺楼主2024/1/27 21:46
#include<bits/stdc++.h>
using namespace std;
struct node 
{
	int v,w;
	node(int _v,int _w) {v = _v; w = _w;}
};
int t,n,m,cnt[2005],dis1[2005],dis2[2005],ans = 0x3f3f3f3f;
bool vis[2005];
vector<node> gra[2005];
queue<int> q;
bool spfa1() 
{
	while (!q.empty()) q.pop();
	memset(cnt,0,sizeof(cnt));
	memset(vis,false,sizeof(vis));
	q.push(1);
	vis[1] = true;
	while (!q.empty()) 
	{
		int u = q.front();
		for (auto to: gra[u]) 
		{
			int v = to.v,w = to.w;
			if (dis1[u] + w < dis1[v]) 
			{
				cnt[v] = cnt[u] + 1;
				dis1[v] = dis1[u] + w;
				if (cnt[v] >= n) return true;
				if (!vis[v]) 
				{
					q.push(v);
					vis[v] = true;
				}
			}
		}
		q.pop();
		vis[u] = false;
	}
	return false;
}
bool spfa2() 
{
	while (!q.empty()) q.pop();
	memset(cnt,0,sizeof(cnt));
	memset(vis,false,sizeof(vis));
	q.push(n);
	vis[n] = true;
	while (!q.empty()) 
	{
		int u = q.front();
		for (auto to: gra[u]) 
		{
			int v = to.v,w = to.w;
			if (dis2[u] + w < dis2[v]) 
			{
				cnt[v] = cnt[u] + 1;
				dis2[v] = dis2[u] + w;
				if (cnt[v] >= n) return true;
				if (!vis[v]) 
				{
					q.push(v);
					vis[v] = true;
				}
			}
		}
		q.pop();
		vis[u] = false;
	}
	return false;
}
int main() 
{
	int u,v,w;
	memset(dis1,0x3f,sizeof(dis1));
	memset(dis2,0x3f,sizeof(dis2));
	dis1[1] = 0;
	dis2[n] = 0;
	cin >> n >> m;
	for (int i = 1;i <= m;i++) 
	{
		cin >> u >> v >> w;
		gra[u].push_back(node(v,-w));
	}
	if (spfa1() || spfa2()) cout << "Forever love" << endl;
	else cout << min(dis1[n],dis2[1]) << endl;
	return 0;
}
2024/1/27 21:46
加载中...