WIP

想定解 (c++)

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
    int N,M;
    cin>>N>>M;
    vector<vector<pair<int,int>>> G(N);
    for(int i=0;i<M;i++){
        int a,b,c;
        cin>>a>>b>>c;
        a--;
        b--;
        G[a].push_back({b,c});
        G[b].push_back({a,c});
    }
    priority_queue<tuple<int,int,int>,vector<tuple<int,int,int>>,greater<tuple<int,int,int>>> pq;
    vector<pair<int,int>> dist(N,{1e18,1e18});
    dist[0] = {0,0};
    pq.push({0,0,0});
    while(!pq.empty()){
        int c,w,u;
        tie(c,w,u) = pq.top();
        pq.pop();
        if(dist[u] != make_pair(c,w)) continue;
        for(pair<int,int> y:G[u]){
            int v,x;
            tie(v,x) = y;
            pair<int,int> now;
            if(x == -1) now = {c+1,w+1};
            else now = {c,max(w+1,x+1)};
            if(dist[v] <= now) continue;
            dist[v] = now;
            pq.push({dist[v].first,dist[v].second,v});
        }
    }
    cout<<dist[N-1].second<<endl;
}