yukicoder 277 根掘り葉掘り

2015/09/06 (Sun) yukicoder 最短経路 グラフ

問題

問題文

方針

木の外にもう $1$ つの頂点 $v$ を作って，根と葉に重さ $0$ の辺をつなぎ， $v$ からダイクストラ(BFS)して出力するだけ．

なぜ本番に思いつかなかったんだ…

実装

signed main(){
    int N;
    cin >> N;
    Graph g(N+1);
    rep(i,N-1){
        int a,b;
        cin >> a >> b;
        a--, b--;
        g[a].eb(a,b,1);
        g[b].eb(b,a,1);
    }
    int s = N;
    rep(i,N) if(g[i].size()==1) g[s].eb(s,i,0);
    g[s].eb(s,0,0);
    vi d = dijkstra(g,s);
    rep(i,N) cout << d[i] << endl;
}