結果

問題 No.807 umg tours
コンテスト
ユーザー polyomino_24
提出日時 2019-03-22 23:58:08
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,774 bytes
コンパイル時間 767 ms
コンパイル使用メモリ 103,876 KB
最終ジャッジ日時 2024-11-14 21:21:29
合計ジャッジ時間 1,671 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.cpp:49:1: error: ‘dijkstra’ function uses ‘auto’ type specifier without trailing return type
   49 | auto dijkstra(int s,vector<vector<edge>>&g){
      | ^~~~
main.cpp:49:1: note: deduced return type only available with ‘-std=c++14’ or ‘-std=gnu++14’

ソースコード

diff # 

#include <algorithm>
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <vector>
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
//#define cerr if(false) cerr
#define show(...) cerr << #__VA_ARGS__ << " = ", debug(__VA_ARGS__);
using namespace std;
using ll = long long;
using pii = pair<int,int>;
template<typename T, typename S>
ostream &operator<<(ostream &os, pair<T, S> a){
    os << '(' << a.first << ',' << a.second << ')';
    return os;
}
template<typename T>
ostream &operator<<(ostream &os, vector<T> v){
    for(auto x:v)os << x << ' ';
    return os;
}
void debug(){cerr << '\n';}
template<typename H, typename... T>
void debug(H a, T... b){
    cerr << a;
    if(sizeof...(b))cerr << ", ";
    debug(b...);
}
struct edge{
    int to, cost;
    edge(int a = 0, int b = 0) : to(a), cost(b) {}
};
auto dijkstra(int s,vector<vector<edge>>&g){
    int n = (int)g.size();
    vector<vector<ll>>dist(2);
    rep(i,2)dist[i].resize(n,1LL<<60);
//    vector<ll> way(n,0);
    using ll_i = pair<ll,pii>;
    priority_queue<ll_i,vector<ll_i>,greater<ll_i>>pq;
    dist[0][s] = 0;
    dist[1][s] = 0;
//    way[s] = 1;
    rep(i,2)pq.push({dist[i][s],pii(i,s)});
    while(!pq.empty()){
        auto a = pq.top();
        pq.pop();
        int s = a.second.first;
        int v = a.second.second;
        if(a.first > dist[s][v])continue;
        for(auto &x:g[v]){
            if(dist[s][x.to] > dist[s][v] + x.cost){
                dist[s][x.to] = dist[s][v] + x.cost;
//                way[x.to] = 0;
                pq.push({dist[s][x.to], pii(s,x.to)});
            }
            if(s == 0){
                if(dist[1][x.to] > dist[s][v]){
                    dist[1][x.to
                            ] = dist[s][v];
                    //                way[x.to] = 0;
                    pq.push({dist[1][x.to], pii(1,x.to)});
                }
            }
//            if(dist[x.to] == dist[v] + x.cost){
//                way[x.to] += way[v];
//                way[x.to] %= mod;
//            }
        }
    }
//    return {dist, way};
    return dist;
}
int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n,m;
    cin >> n >> m;
    vector<vector<edge>>g;
    g.resize(n);
    rep(i,m){
        int a,b;
        ll c;
        cin >> a >> b >> c;
        a--,b--;
        g[a].emplace_back(b,c);
        g[b].emplace_back(a,c);
    }
    auto d = dijkstra(0, g);
    rep(i,n){
        cout << d[0][i] + d[1][i] << "\n";
    }
}
0