Submission #4635897

---

Source Code Expand

#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include<unordered_map>
#include<queue>
#include<functional>

using namespace std;

using ll = long long int;
using pll = pair<ll, ll>;

int n, m;
struct Edge{
    ll cost, to;
    Edge(ll c, ll t) : cost(c), to(t){}
};
unordered_map<ll, vector<Edge>> g;
unordered_map<ll, ll> d;

ll get_id(ll p, ll c){
    return p + n * c;
}

void add_edge(ll p, ll q, ll c){
    g[get_id(p, c)].push_back({0, get_id(q, c)});
    g[get_id(q, c)].push_back({0, get_id(p, c)});
    g[get_id(p, c)].push_back({0, get_id(p, 0)});
    g[get_id(p, 0)].push_back({1, get_id(p, c)});
    g[get_id(q, c)].push_back({0, get_id(q, 0)});
    g[get_id(q, 0)].push_back({1, get_id(q, c)});
}

int main(){
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        int p, q, c;
        cin >> p >> q >> c;
        add_edge(p, q, c);
    }
    priority_queue<pll, vector<pll>, greater<pll>> q;
    d[get_id(1, 0)] = 0;
    q.push({0, get_id(1, 0)});
    while(!q.empty()){
        auto from = q.top(); q.pop();
        for(auto&& t : g[from.second]){
            if(d.find(t.to) == d.end() || d[t.to] > d[from.second] + t.cost){
                d[t.to] = d[from.second] + t.cost;
                q.push({d[t.to], t.to});
            }
        }
    }
    if(d.find(get_id(n, 0)) == d.end()){
        cout << -1 << endl;
    }else{
        cout << d[get_id(n, 0)] << endl;
    }
    return 0;
}

Submission Info

Judge Result