結果

提出番号	2366
提出者	kya
言語	C++
提出日時	2020-04-27 21:31:04
問題名	(49)最短経路問題
結果	AC
点数	100%

---

テストケース

ソースコード

#include <bits/stdc++.h>
using namespace std;

template<typename T>
struct Edge {
    int to; T cost;
    Edge (int to, T cost = 1) : to(to), cost(cost) { }
    bool operator< (const Edge &r) const { return (cost < r.cost); }
};

template<typename T>
using Graph = vector<vector<Edge<T>>>;

template <typename T>
vector<T> dijkstra(const Graph<T> &g, int s){
    using P = pair<T, int>;
    vector<T> ret(g.size(), -1);
    priority_queue<P, vector<P>, greater<P>> que;
    que.emplace(ret[s], s); ret[s] = 0;
    while (not que.empty()) {
        int v; T c; tie(c, v) = que.top(); que.pop();
        if (ret[v] < c) continue;
        for (const auto &e : g[v]) {
            if (ret[e.to] > ret[v] + e.cost or ret[e.to] == -1) {
                ret[e.to] = ret[v] + e.cost;
                que.emplace(ret[e.to], e.to);
            }
        }
    }
    return ret;
}

int main() {
    int n, m;
    cin >> n >> m;
    
    Graph<long long> g(n + 1);
    
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        g[a].emplace_back(b, c);
        g[b].emplace_back(a, c);
    }
    
    vector<long long> ans = dijkstra(g, 1);
    cout << ans[n] << '\n';
    
    return 0;
}