特殊点(5pts)

• 直接输出$-1$,找不到。

dijkstra最短路(35pts)

• $dist[i]$表示从0走到$i$的最短距离，因为只能是$k$的倍数，根据之前做类似题目的经验，$dist[i][j]$ 表示走到点$i$余数为$j$的最短距离。

#include<bits/stdc++.h>
using namespace std;
const int N=2e4+10,M=110;
int h[N],e[N],w[N],ne[N],idx;
int n,m,k;
int dist[N][M];
bool st[N][M];
typedef pair<int,int> PII;
struct Node{
    int u,ti,d; //u是图中节点编号,i是对于时间的分层,d是走到u时间为i系列的最短距离
    bool operator<(const Node &W)const //重载了大根堆
    {
        return d>W.d;
    }
};
void add(int a,int b,int c)
{
    e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
void dijkstra()
{
    priority_queue<Node> q;
    memset(dist,0x3f,sizeof dist);
    dist[1][0]=0;
    q.push({1,0,0});
    while(q.size())
    {
        auto t=q.top();
        q.pop();
        int u=t.u,ti=t.ti;//获取当前点和时间
        if(st[u][ti]) continue;//已经走过(冗余备份)
        st[u][ti]=true;
        for(int i=h[u];i!=-1;i=ne[i])
        {
            int v=e[i],d1=w[i]; //走到的点和开放的时刻
            int j=(ti+1)%k;//走到的当前点的时刻
            int t=dist[u][ti];
            if(dist[v][j]>t+1)
            {
                dist[v][j]=t+1;
                q.push({v,j,t+1});
            }
        }
    }
    
}
int main()
{
    cin>>n>>m>>k;
    memset(h,-1,sizeof h);
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
    }
    dijkstra();
    if(dist[n][0]==0x3f3f3f3f)
    {
        dist[n][0]=-1;
    }

    cout<<dist[n][0];
    return 0;
}

dijkstra(100pts)

• 我们需要额外考虑没有开放的情况,那么走到当前位置没有开放，我们就同时间差推迟开始的时间即可。

#include<bits/stdc++.h>
using namespace std;
const int N=2e4+10,M=110;
int h[N],e[N],w[N],ne[N],idx;
int n,m,k;
int dist[N][M];
bool st[N][M];
typedef pair<int,int> PII;
struct Node{
    int u,ti,d; //u是图中节点编号,i是对于时间的分层,d是走到u时间为i系列的最短距离
    bool operator<(const Node &W)const //重载了大根堆
    {
        return d>W.d;
    }
};
void add(int a,int b,int c)
{
    e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
void dijkstra()
{
    priority_queue<Node> q;
    memset(dist,0x3f,sizeof dist);
    dist[1][0]=0;
    q.push({1,0,0});
    while(q.size())
    {
        auto t=q.top();
        q.pop();
        int u=t.u,ti=t.ti;//获取当前点和时间
        if(st[u][ti]) continue;//已经走过(冗余备份)
        st[u][ti]=true;
        for(int i=h[u];i!=-1;i=ne[i])
        {
            int v=e[i],d1=w[i]; //走到的点和开放的时刻
            int j=(ti+1)%k;//走到的当前点的时刻
            int t=dist[u][ti];
            if(t<d1) //说明还没有开放
            {
                t+=(d1-t+k-1)/k*k;//累加到最早开放的点(前面必须是c的倍数)
            }
            if(dist[v][j]>t+1)
            {
                dist[v][j]=t+1;
                q.push({v,j,t+1});
            }
        }
    }
    
}
int main()
{
    cin>>n>>m>>k;
    memset(h,-1,sizeof h);
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
    }
    dijkstra();
    if(dist[n][0]==0x3f3f3f3f)
    {
        dist[n][0]=-1;
    }

    cout<<dist[n][0];
    return 0;
}