P1813 拯救小tim

· · 题解

如果 b, e, c 开到 1e9 题解中的做法会 TLE

实际上有 \mathcal O(m \times (n+m) \log m) 的做法。

若存在一条路使得在每一条马路上时间都没有卡在时间上限，那么至少可以在 s 路口多停留一个单位时间。依此类推，最优答案必然走过一条刚好卡在时间上限的马路。那么我们枚举这条马路，从这条马路的两个路口分别出发(提前建好反向边)走到 s 和 t，最后统计答案即可。

所以枚举每条边跑 dij / spfa 就行了

code

#include <bits/stdc++.h>
using namespace std;
int n, m, beg, end, x, y, xx, yy, z, ans = 707406378;
int disa[1000001], disb[1000001], team[1000001], teamb[1000001];
int tot, next[1000001], first[1000001], front[1000001], 
    go[1000001], ta[1000001], tb[1000001], value[1000001];
int totb, nextb[1000001], firstb[1000001], frontb[1000001], 
    gob[1000001], tab[1000001], tbb[1000001], valueb[1000001];
void Add(int x, int y, int xx, int yy, int z)
{
    next[++tot] = first[x];
    first[x] = tot;
    front[tot] = x;
    go[tot] = y;
    ta[tot] = xx;
    tb[tot] = yy;
    value[tot] = z;
}
void Addd(int x, int y, int xx, int yy, int z)
{
    nextb[++totb] = firstb[x];
    firstb[x] = totb;
    frontb[totb] = x;
    gob[totb] = y;
    tab[totb] = xx;
    tbb[totb] = yy;
    valueb[totb] = z;
}
void SpfaOne(int x, int ti)
{
    int t = 0, w = 1;
    team[w] = x;
    disa[x] = 0;
    while (t < w)
    {
        int u = team[++t];
        for (int i = first[u]; i; i = next[i])
        {
            int v = go[i];
            if (disa[u] + ti + value[i] <= tb[i])
            {
                if (disa[u] + ti < ta[i])
                {
                    if (disa[v] > ta[i] + value[i] - ti)
                    {
                        disa[v] = ta[i] + value[i] - ti;
                        team[++w] = v;
                    }
                }
                else if (disa[v] > disa[u] + value[i])
                {
                    disa[v] = disa[u] + value[i];
                    team[++w] = v;
                }
            }
        }
    }
}
void SpfaTwo(int x, int ti)
{
    int t = 0, w = 1;
    teamb[w] = x;
    disb[x] = 0;
    while (t < w)
    {
        int u = teamb[++t];
        for (int i = firstb[u]; i; i = nextb[i])
        {
            int v = gob[i];
            if (ti - disb[u] - valueb[i] >= tab[i])
            {
                if (ti - disb[u] > tbb[i])
                {
                    if (disb[v] > ti - tbb[i] + valueb[i])
                    {
                        disb[v] = ti - tbb[i] + valueb[i];
                        teamb[++w] = v;
                    }
                }
                else if (disb[v] > disb[u] + valueb[i])
                {
                    disb[v] = disb[u] + valueb[i];
                    teamb[++w] = v;
                }
            }
        }
    }
}
int main()
{
    freopen("road.in", "r", stdin);
    freopen("road.out", "w", stdout);
    scanf("%d%d%d%d", &n, &m, &beg, &end);
    for (int i = 1; i <= m; ++i)
    {
        scanf("%d%d%d%d%d%", &x, &y, &xx, &yy, &z);
        if (z <= yy - xx) // 若开放的时间都不够通过则不需要这一条边 
        {
            Add(x, y, xx, yy, z);
            Addd(y, x, xx, yy, z);// 反向边
        }
    }
    for (int i = 1; i <= tot; ++i)
    {
        for (int j = 1; j <= n; ++j) disa[j] = disb[j] = 707406378;
        SpfaOne(go[i], tb[i]);// 跑到终点
        SpfaTwo(front[i], tb[i] - value[i]); // 跑到起点
        if (ans > disa[end] + disb[beg] + value[i]) // 更新最小值
            ans = disa[end] + disb[beg] + value[i];
    }
    if (ans < 707406378)
        printf("%d", ans);
    else printf("Impossible"); // 无解
    fclose(stdin), fclose(stdout);
}