P1813题解

_Anonymous_ · 2023-08-23 11:53:42 · 题解

1.不考虑每条边开始结束时间

就是最简单的最短路，也无负权环，所以 Dijkstra 或者 SPFA 都可以。

选择了 SPFA，dis_i 存储到点 i 最早的时间。

注：SPFA 时，点可能重复进队，所以开一个单向链表，l_i 表示队列中第 i 个点的后继，若为 0 则说明不在队中，若为 -1 说明是队尾，队列不为空时，头指针不为 -1。

2.不考虑在起点等待，考虑每条边开始结束时间

• 在建图的时候把通过时间不够的边删去，即 b+c>e 的边

• 在 SPFA 松弛边进队时多进行一个判断，即 dis_u+i.c\leq i.e 判断到当前点的时间够不够通过当前边

• 在松弛时，当前边的开始时间 i.b 与到达当前点时间 dis_u 取大值松弛 dis_{i.to}=\max(i.b,dis_u)+i.c，判断同理

3.考虑在起点等待

建图时存一下最早开始的边的开始时间 mntim，最晚出发能通过的边的时间 mxtim，遍历 [mntim,mxtim] 即可。

4.一些细节

由于取出队头后队列可能为空，但是队头会更新新的点进队，所以队头的后移可以放在松弛之后

在起点等待的时间要存进 dis_s 里

5.代码

#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;
    l[s] = -1, hd = tl = s;
    while(hd != -1)
    {
        int u = hd;
        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(dis[t] == -1)
        {
            break;
        }
    }
    if(ans == -1)
    {
        cout << "Impossible" << endl;
        return 0;
    }
    cout << ans << endl;
    return 0;
}