結果

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

テストケース

テストケース 結果 得点 実行時間 メモリ使用量
1 AC 100% 2ms 8544KB
2 AC 100% 2ms 8544KB
3 AC 100% 2ms 8544KB
4 AC 100% 2ms 8544KB
5 AC 100% 2ms 8464KB
6 AC 100% 6ms 7600KB
7 AC 100% 7ms 8096KB
8 AC 100% 7ms 7872KB
9 AC 100% 6ms 8560KB
10 AC 100% 7ms 8096KB
11 AC 100% 273ms 61968KB
12 AC 100% 292ms 61888KB
13 AC 100% 280ms 62000KB
14 AC 100% 273ms 61856KB
15 AC 100% 256ms 58160KB
16 AC 100% 327ms 61872KB
17 AC 100% 314ms 61952KB
18 AC 100% 320ms 61872KB
19 AC 100% 305ms 61904KB
20 AC 100% 319ms 61904KB
21 AC 100% 302ms 61872KB
22 AC 100% 333ms 61872KB
23 AC 100% 298ms 61728KB
24 AC 100% 331ms 61904KB
25 AC 100% 319ms 61840KB
26 AC 100% 324ms 61936KB
27 AC 100% 318ms 61952KB
28 AC 100% 317ms 61952KB
29 AC 100% 332ms 61872KB
30 AC 100% 315ms 61904KB

ソースコード

#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;
}