5310. 旅游巴士

这是TLE代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>

#define x first
#define y second

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pii;

const int N = 20000 + 10, M = N << 1, K = 110;

priority_queue <pii , vector <pii>, greater <pii> > q;

int n,m,k;
ll dist[N][K];
bool st[N][K];
ll h[N], e[M], ne[M], w[M];
int idx;

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

void dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1][0] = 0;

    q.push({0, 1});
    while(!q.empty())
    {
        auto t = q.top();
        q.pop();
        ll u = t.y, distance = t.x;

        if (st[u][distance % k]) 
            continue;

        st[u][distance % k] = true;

        for (register int i = h[u]; ~i; i = ne[i])
        {
            int j = e[i];
            ll s = (distance + 1) % k;

            if (distance >= w[i]) 
                s = distance;
            else s = ((w[i] - distance + k - 1) / k) * k + distance;

            if (dist[j][(s + 1) % k] > s + 1)
            {
                dist[j][(s + 1) % k] = s + 1;
                q.push({s + 1, j});
            }
        }
    }
}

inline int read()
{
    register int x = 0, f = 1;
    register char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
        x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
    return x * f;
}

int main()
{
    n = read(), m = read(), k = read();

    memset(h, -1, sizeof h);
    for (register int i = 1; i <= m; i ++ )
    {
        int a = read(), b = read(), c = read();
        add(a, b, c);
    }

    dijkstra();

    if (!st[n][0]) 
        puts("-1");
    else printf("%lld",dist[n][0]);

    return 0;
}

这是AC代码

#pragma GCC optimize(3)
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC optimize(2)

#include <cstdio>
#include <cstring>
#include <queue>

#define x first
#define y second

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pii;

const int N = 20000 + 10, M = N << 1, K = 110;

priority_queue <pii , vector <pii>, greater <pii> > q;

int n,m,k;
ll dist[N][K];
bool st[N][K];
ll h[N], e[M], ne[M], w[M];
int idx;

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

void dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1][0] = 0;

    q.push({0, 1});
    while(!q.empty())
    {
        auto t = q.top();
        q.pop();
        ll u = t.y, distance = t.x;

        if (st[u][distance % k]) 
            continue;

        st[u][distance % k] = true;

        for (register int i = h[u]; ~i; i = ne[i])
        {
            int j = e[i];
            ll s = (distance + 1) % k;

            if (distance >= w[i]) 
                s = distance;
            else s = ((w[i] - distance + k - 1) / k) * k + distance;

            if (dist[j][(s + 1) % k] > s + 1)
            {
                dist[j][(s + 1) % k] = s + 1;
                q.push({s + 1, j});
            }
        }
    }
}

inline int read()
{
    register int x = 0, f = 1;
    register char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
        x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
    return x * f;
}

void write(ll x) 
{
    if (x < 0) 
        putchar('-'), x = -x;
    if (x > 9) 
        write(x / 10);
    putchar(x % 10 + '0');
    return;
}

int main()
{
    n = read(), m = read(), k = read();

    memset(h, -1, sizeof h);
    for (register int i = 1; i <= m; i ++ )
    {
        int a = read(), b = read(), c = read();
        add(a, b, c);
    }

    dijkstra();

    if (!st[n][0]) 
        puts("-1");
    else write(dist[n][0]);

    return 0;
}