結果

問題 No.1473 おでぶなおばけさん
ユーザー ooaiu
提出日時 2025-02-05 18:17:43
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 232 ms / 2,000 ms
コード長 1,104 bytes
コンパイル時間 8,534 ms
コンパイル使用メモリ 298,528 KB
実行使用メモリ 12,264 KB
最終ジャッジ日時 2025-02-05 18:18:03
合計ジャッジ時間 19,520 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 47
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <atcoder/dsu>
using namespace std;
using ll = long long;
int main() {
	int N, M;
	cin >> N >> M;
	vector<array<int, 3>> E;
	vector<int> U(M), V(M), W(M);
	for(int i = 0; i < M; i++) {
		cin >> U[i] >> V[i] >> W[i];
		U[i]--, V[i]--;
		E.push_back({-W[i], U[i], V[i]});
	}
	vector<vector<pair<int, int>>> adj(N);
	sort(E.begin(), E.end());
	vector<bool> seen(M);
	atcoder::dsu uf(N);
	int id = 0;
	int x = -1;
	for(const auto&[w, u, v] : E) {
		if(!uf.same(u, v)) {
			uf.merge(u, v);
			adj[u].push_back({v, -w});
			adj[v].push_back({u, -w});
			seen[id] = true;
		}
		if(uf.same(0, N - 1)) x = max(x, -w);
		id++;
	}
	for(int i = 0; i < M; i++) if(!seen[i] && x <= -E[i][0]) {
		adj[E[i][1]].push_back({E[i][2], -E[i][0]});
		adj[E[i][2]].push_back({E[i][1], -E[i][0]});
	}
	queue<int> que;
	que.push(0);
	vector<int> dist(N, -1);
	dist[0] = 0;
	while(!que.empty()) {
		int v = que.front();
		que.pop();
		for(const auto&[to, cst]: adj[v]) {
			if(dist[to] == -1) {
				dist[to] = dist[v] + 1;
				que.push(to);
			}
		}
	}
	cout << x << " " << dist[N - 1] << endl;
}
0