結果

問題 No.807 umg tours
ユーザー yuliicppyyuliicppy
提出日時 2019-07-01 11:27:28
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 3,067 bytes
コンパイル時間 971 ms
コンパイル使用メモリ 101,112 KB
実行使用メモリ 42,804 KB
最終ジャッジ日時 2023-09-22 19:07:53
合計ジャッジ時間 8,279 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 2 ms
4,380 KB
testcase_04 AC 2 ms
4,376 KB
testcase_05 AC 2 ms
4,376 KB
testcase_06 AC 2 ms
4,376 KB
testcase_07 AC 2 ms
4,380 KB
testcase_08 AC 1 ms
4,376 KB
testcase_09 AC 2 ms
4,376 KB
testcase_10 AC 1 ms
4,376 KB
testcase_11 AC 287 ms
32,464 KB
testcase_12 AC 316 ms
25,708 KB
testcase_13 AC 428 ms
35,004 KB
testcase_14 AC 166 ms
16,872 KB
testcase_15 AC 128 ms
14,280 KB
testcase_16 AC 441 ms
37,072 KB
testcase_17 AC 550 ms
42,512 KB
testcase_18 AC 559 ms
42,692 KB
testcase_19 AC 550 ms
42,048 KB
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 AC 263 ms
32,348 KB
testcase_25 AC 557 ms
42,804 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <cmath>
#include <tuple>
#include <cstdio>
#include <bitset>
#include <sstream>
#include <iterator>
#include <numeric>
#include <map>
#include <cstring>
#include <set>
#include <functional>
#include <iomanip>

using namespace std;

#define DEBUG_ //!!提出時にコメントアウト!!
#ifdef DEBUG_
	#define dump(x)  cerr << #x << " = " << (x) << endl;
#else
	#define dump(x)  ;
#endif

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SZ(x) ((int)(x).size())
#define pb push_back
#define eb emplace_back

//#define int long long

typedef long long LL;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

template <typename T>
std::string printVector(const std::vector<T> &data)
{
    std::stringstream ss;
    std::ostream_iterator<T> out_it(ss, ", ");
    ss << "[";
    std::copy(data.begin(), data.end() - 1, out_it);
    ss << data.back() << "]";
    return ss.str();
}

const int MOD = 1e9+7;
const LL LINF = 1001002003004005006ll;
const int INF = 1001001001;

template< typename T >
struct edge {
  int src, to;
  T cost;
  edge(int to, T cost) : src(-1), to(to), cost(cost) {}
  edge(int src, int to, T cost) : src(src), to(to), cost(cost) {}
  edge &operator=(const int &x) {
    to = x;
    return *this;
  }
  operator int() const { return to; }
};
template< typename T >
using Edges = vector< edge< T > >;
template< typename T >
using WeightedGraph = vector< Edges< T > >;
using UnWeightedGraph = vector< vector< int > >;
template< typename T >
using Matrix = vector< vector< T > >;

template< typename T >
vector< T > dijkstra(WeightedGraph< T > &g, int s) {
  const auto INF = numeric_limits< T >::max();
  vector< T > dist(g.size(), INF);

  using Pi = pair< T, int >;
  priority_queue< Pi, vector< Pi >, greater< Pi > > que;
  dist[s] = 0;
  que.emplace(dist[s], s);
  while(!que.empty()) {
    T cost;
    int idx;
    tie(cost, idx) = que.top();
    que.pop();
    if(dist[idx] < cost) continue;
    for(auto &e : g[idx]) {
      auto next_cost = cost + e.cost;
      if(dist[e.to] <= next_cost) continue;
      dist[e.to] = next_cost;
      que.emplace(dist[e.to], e.to);
    }
  }
  return dist;
}

signed main(int argc, char const *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N,M; cin >> N >> M;
    WeightedGraph<int> g1(N);
    WeightedGraph<int> g2(2*N);

    REP(i,M){
        int a,b,c; cin >> a >> b >> c;
        a--; b--;
        g1[a].eb(b,c);
        g1[b].eb(a,c);

        g2[a*2].eb(b*2,c);
        g2[b*2].eb(a*2,c);
        g2[a*2+1].eb(b*2+1,c);
        g2[b*2+1].eb(a*2+1,c);

        g2[a*2].eb(b*2+1,0);
        g2[b*2].eb(a*2+1,0);
    }
    auto r1 = dijkstra(g1,0);
    auto r2 = dijkstra(g2,0);

    REP(i,N){
        if(i == 0){
             cout << 0 << endl;
             continue;
        }
        cout << r1[i]+r2[i*2+1] << endl;
    }


}
0