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了