結果
問題 | No.277 根掘り葉掘り |
ユーザー |
![]() |
提出日時 | 2016-05-07 20:37:54 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 281 ms / 3,000 ms |
コード長 | 1,083 bytes |
コンパイル時間 | 511 ms |
コンパイル使用メモリ | 70,036 KB |
実行使用メモリ | 10,552 KB |
最終ジャッジ日時 | 2024-10-05 10:24:08 |
合計ジャッジ時間 | 4,344 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
#include <iostream>#include <vector>#include <algorithm>#include <queue>using namespace std;#define RREP(i,s,e) for (i = s; i >= e; i--)#define rrep(i,n) RREP(i,(int)(n)-1,0)#define REP(i,s,e) for (i = s; i <= e; i++)#define rep(i,n) REP(i,0,(int)(n)-1)#define INF 100000000typedef long long ll;vector<int> e[100000];int dist[100000];void dijkstra(int x) {priority_queue<pair<int,int>> q;dist[x] = 0;q.push(make_pair(0,x));while (!q.empty()) {int from = q.top().second;q.pop();for (auto to : e[from]) {if (dist[to] > dist[from] + 1) {dist[to] = dist[from] + 1;q.push(make_pair(-dist[to],to));}}}}int main() {int i, n;cin >> n;rep (i,n-1) {int x, y;cin >> x >> y;x--; y--;e[x].push_back(y);e[y].push_back(x);}rep (i,n) dist[i] = INF;dijkstra(0);REP (i,1,n) if (e[i].size() == 1)dijkstra(i);rep (i,n)cout << dist[i] << endl;return 0;}