結果

問題 No.1473 おでぶなおばけさん
ユーザー miscalc
提出日時 2021-04-09 22:36:37
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 132 ms / 2,000 ms
コード長 2,767 bytes
コンパイル時間 1,965 ms
コンパイル使用メモリ 186,136 KB
実行使用メモリ 14,720 KB
最終ジャッジ日時 2024-06-25 06:14:32
合計ジャッジ時間 7,771 ms
ジャッジサーバーID
(参考情報)
judge5 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 47
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using pll = pair<ll, ll>;
constexpr ll MOD = 1e9 + 7;
//constexpr ll MOD = 998244353;
//constexpr ll MOD = ;
ll mod(ll A, ll M) {return (A % M + M) % M;}
constexpr ll INF = 1LL << 60;
template<class T> bool chmin(T& a, T b) {if (a > b) {a = b; return true;} return false;}
template<class T> bool chmax(T& a, T b) {if (a < b) {a = b; return true;} return false;}
ll divceil(ll A, ll B) {return (A + (B - 1)) / B;}
#define FINALANS(A) do {cout << (A) << '\n'; exit(0);} while (false)
template <class Abel> class unionfind
{
public:
vector<ll> parent;
vector<ll> rank;
vector<Abel> diffw;
unionfind(ll N, Abel U = 0)
{
parent = vector<ll>(N, -1);
rank = vector<ll>(N, 0);
diffw = vector<Abel>(N, U);
}
ll root(ll X)
{
if (parent.at(X) < 0) return X;
ll R = root(parent.at(X));
diffw.at(X) += diffw.at(parent.at(X));
return parent.at(X) = R;
}
ll size(ll X)
{
return -parent.at(root(X));
}
Abel weight(ll X)
{
root(X);
return diffw.at(X);
}
Abel diff(ll X, ll Y)
{
return weight(Y) - weight(X);
}
bool same(ll X, ll Y)
{
return (root(X) == root(Y));
}
bool unite(ll X, ll Y, Abel W = 0)
{
W += weight(X);
W -= weight(Y);
X = root(X);
Y = root(Y);
if (X == Y) return false;
if (rank.at(X) < rank.at(Y))
{
swap(X, Y);
W = -W;
}
if (rank.at(X) == rank.at(Y)) rank.at(X)++;
parent.at(X) += parent.at(Y);
parent.at(Y) = X;
diffw.at(Y) = W;
return true;
}
};
int main()
{
ll N, M;
cin >> N >> M;
using tlll = tuple<ll, ll, ll>;
vector<tlll> DST(M);
for (ll i = 0; i < M; i++)
{
ll s, t, d;
cin >> s >> t >> d;
s--, t--;
DST.at(i) = make_tuple(d, s, t);
}
sort(DST.begin(), DST.end(), greater<tlll>());
unionfind<ll> uf(N);
ll maxw = INF;
for (ll i = 0; i < M; i++)
{
ll d = get<0>(DST.at(i)), s = get<1>(DST.at(i)), t = get<2>(DST.at(i));
if (!uf.same(s, t))
{
uf.unite(s, t);
if (uf.same(0, N - 1))
{
maxw = d;
break;
}
}
}
cout << maxw << " ";
vector<vector<ll>> G(N);
for (ll i = 0; i < M; i++)
{
ll d = get<0>(DST.at(i)), s = get<1>(DST.at(i)), t = get<2>(DST.at(i));
if (maxw <= d)
{
G.at(s).push_back(t);
G.at(t).push_back(s);
}
}
queue<ll> que;
vector<ll> dist(N, -1);
que.push(0);
dist.at(0) = 0;
while (!que.empty())
{
ll v = que.front();
que.pop();
for (auto nv : G.at(v))
{
if (dist.at(nv) != -1)
continue;
dist.at(nv) = dist.at(v) + 1;
que.push(nv);
}
}
cout << dist.at(N - 1) << endl;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0