P1813请求加强数据
  • 板块学术版
  • 楼主_Anonymous_
  • 当前回复1
  • 已保存回复1
  • 发布时间2023/8/23 10:43
  • 上次更新2023/11/3 01:49:19
查看原帖
P1813请求加强数据
381926
_Anonymous_楼主2023/8/23 10:43

rt,下面这份代码现在可以AC

#include<bits/stdc++.h>
#define debug cout << "OK" << endl;
#define MAXN int(1e2 + 10)
#define MAXM int(1e3 + 10)
using namespace std;

struct edge{
	int nxt, to, bg, en, c;
}e[MAXM];
int head[MAXN], tot;

void init()
{
	memset(head, -1, sizeof(head));
	tot = 0;
}

void add(int u, int v, int bg, int en, int c)
{
	e[tot].to = v, e[tot].bg = bg, e[tot].c = c, e[tot].en = en, e[tot].nxt = head[u];
	head[u] = tot++;
}

int n, m, s, t;
int mxtim, mntim = 1e9;

int dis[MAXN], ans = -1;
int l[MAXN], hd, tl;

void SPFA(int tim)
{
	memset(dis, -1, sizeof(dis));
	dis[s] = tim;
	memset(l, 0, sizeof(l));
	l[s] = -1, hd = tl = s;
	while(hd != -1)
	{
		int u = hd;
		if(u == t)//到终点不能直接退出,有可能还有边要松弛,松弛后可能有更快的路 
		{
			if(ans == -1)
			{
				ans = dis[t] - tim;
			}
			ans = min(ans, dis[t] - tim);
		}
		if(head[u] == -1)
		{
			hd = l[u];
			l[u] = 0;
			continue;
		}
		for(edge i = e[head[u]];; i = e[i.nxt])
		{
			//这条边的开始时间时出发一定可以到这条边终点,所以只用看到这条边时出发能不能到这条边终点 
			//到终点的时间小于原时间/没到过这个点则松弛
			if(dis[u] + i.c <= i.en && (max(dis[u], i.bg) + i.c < dis[i.to] || dis[i.to] == -1))
			{
				dis[i.to] = max(dis[u], i.bg) + i.c;
				if(!l[i.to])//不在队列中则进队 
				{
					l[tl] = i.to;
					tl = i.to;
					l[tl] = -1;
				} 
			}
			if(i.nxt == -1)
			{
				break;
			}
		}
		hd = l[u];
		l[u] = 0;
	}
	if(dis[t] != -1)
	{
		if(ans == -1)
		{
			ans = dis[t] - tim;
		}
		ans = min(ans, dis[t] - tim);
	}
}

int main()
{
	cin >> n >> m >> s >> t;
	init();
	for(int i = 1; i <= m; i++)
	{
		int u, v, bg, en, c;
		scanf("%d %d %d %d %d", &u, &v, &bg, &en, &c);
		if(bg + c > en)
		{
			continue;
		}
		add(u, v, bg, en, c);
		mxtim = max(mxtim, en);
		mntim = min(mntim, en);//这里错得十分睿智
	}
	for(int i = mntim; i <= mxtim; i++)
	{
		SPFA(i);
	}
	if(ans == -1)
	{
		cout << "Impossible" << endl;
		return 0;
	}
	cout << ans << endl;
 	return 0;
}

/*
4 5 1 4 
1 2 0 5 1 
1 2 0 5 2 
1 3 1 5 2 
2 4 3 5 1 
3 4 3 5 1 
*/

连末尾的数据都过不了,但是AC了

2023/8/23 10:43
加载中...