Submission #2377928

---

Source Code Expand

#include <bits/stdc++.h>

#define rep(n) for(int i=0;i<n;i++)
#define repp(j, n) for(int j=0;j<n;j++)
#define reppp(i, m, n) for(int i=m;i<n;i++)
#define all(c) c.begin(), c.end()
#define rall(c) c.rbegin(), c.rend()
#define debug(x) cerr << #x << ": " << x << endl;

using namespace std;

typedef long long ll;
typedef pair<ll, ll> Pll;
typedef pair<int, int> Pii;

map<ll, ll> d;
priority_queue< Pll, vector<Pll>, greater<Pll> > que;
map<ll, vector<Pll> > edges;
map<ll, bool> ok;
ll n,m,p,r,c;

void dijkstra(ll start){
    d[start] = 0LL;
    que.push(Pll(0LL, start));

    while(!que.empty()){
        Pll v = que.top(); que.pop();
        ok[v.second/(m+1LL)] = true;
        if(d.find(v.second) != d.end() && d[v.second] < v.first) continue;
        for(Pll e: edges[v.second]){
            if(d.find(e.first) == d.end() || d[e.first] > d[v.second] + e.second){
                d[e.first] = d[v.second] + e.second;
                que.push(Pll(d[e.first], e.first));
            }
        }
    }
}

int main() {
    std::ios::sync_with_stdio(0); cin.tie(0);

    cin >> n >> m;
    rep(m){
        cin >> p >> r >> c;
        p--; r--;
        if(p == 0) ok[r] = true;
        if(r == 0) ok[p] = true;
        edges[p*(m+1LL)+c].emplace_back(r*(m+1LL)+c, 0LL);
        edges[r*(m+1LL)+c].emplace_back(p*(m+1LL)+c, 0LL);
        edges[p*(m+1LL)].emplace_back(p*(m+1LL)+c, 0LL);
        edges[p*(m+1LL)+c].emplace_back(p*(m+1LL), 1LL);
        edges[r*(m+1LL)].emplace_back(r*(m+1LL)+c, 0LL);
        edges[r*(m+1LL)+c].emplace_back(r*(m+1LL), 1LL);
    }

    dijkstra(0LL);
    cout << (ok[n-1]?d[(n-1LL)*(m+1LL)]:-1) << endl;
}

Submission Info

Judge Result