CUBE-T185: Osu! Mapping

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
typedef long long lli;

typedef struct vert{
    lli w;
    int v;
}vert;

typedef struct vstate{
    lli w; // Weight
    int v; // Vertex
    int st; // State
    bool operator < (const vstate &rhs)const{
        return w > rhs.w;
    }
}vstate;

vector<vector<vert>> adj;
int nv, ne, m, s, e;

lli Dijkstra(int s, int e){
    vector<vector<bool>> visited(nv + 1, vector<bool>(m, false));
    vector<vector<lli>> dist(nv + 1, vector<lli>(m, 1e18));
    priority_queue<vstate> q;
    bool found = false;
    dist[s][1 % m] = 0;
    q.push({dist[s][1 % m], s, 1 % m});
    while(!q.empty()){
        int u = q.top().v;
        int st = q.top().st;
        q.pop();
        if(visited[u][st]){
            continue;
        }
        if(u == e && st == 0){
            found = true;
            break;
        }
        visited[u][st] = true;
        for(auto nxt : adj[u]){
            int v = nxt.v;
            int w = nxt.w;
            if(!visited[v][(st + 1) % m] && dist[u][st] + w < dist[v][(st + 1) % m]){
                dist[v][(st + 1) % m] = dist[u][st] + w;
                q.push({dist[v][(st + 1) % m], v, (st + 1) % m});
            }
        }
    }
    if(found){
        return dist[e][0];
    } else {
        return -1;
    }
}

int main(){

    int u, v, w;

    scanf("%d %d %d", &nv, &ne, &m);
    scanf("%d %d", &s, &e);
    adj.assign(nv + 1, vector<vert>());
    for(int i = 1; i <= ne; ++i){
        scanf("%d %d %d", &u, &v, &w);
        adj[u].push_back({w, v});
    }
    cout << Dijkstra(s, e);

    return 0;
}