結果

問題 No.872 All Tree Path
ユーザー MiyanagaTeru
提出日時 2019-09-29 23:13:48
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,260 bytes
コンパイル時間 2,402 ms
コンパイル使用メモリ 199,940 KB
最終ジャッジ日時 2025-01-07 19:57:31
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 6 TLE * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> l_l;
typedef pair<int , int> i_i;
typedef vector<ll> vel;
typedef vector<int> vei;
typedef vector<char> vec;
typedef vector<bool> veb;
typedef vector<string> ves;
typedef vector<vector<ll>> ve_vel;
typedef vector<vector<int>> ve_vei;
typedef vector<vector<char>> ve_vec;
typedef vector<vector<bool>> ve_veb;
typedef vector<vector<string>> ve_ves;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<(int)(n);i++)
#define rep2(i,n) for(int i=2;i<(int)(n);i++)
#define repk(i,k,n) for(int i=k;i<(int)(n);i++)
#define fs first
#define sc second
#define pub push_back
#define puf push_front
#define pob pop_back
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define maxel(a) *max_element(all(a))
#define minel(a) *min_element(all(a))
#define acc accumulate
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define mod (1000000007)
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }


typedef pair<int , int> P;//<最短距離, 頂点番号>
#define MAX_V 200005
struct edge {int to, cost; };
int V;//頂点数
vector<edge> G[MAX_V];
int d[MAX_V];//頂点sからの最短距離

//ABC073,ABC070D


void dijkstra(int s) {
    //greater<P>を指定し.fsを小さい順に取り出す
    priority_queue<P, vector<P>, greater<P> > que;
    fill(d, d+V, INF);
    d[s] = 0;
    que.push(P(0,s));

    while(!que.empty()) {
        P p = que.top(); que.pop();
        int v = p.sc;
        if(d[v] < p.fs) continue;
        rep(i,G[v].size()) {
            edge e = G[v][i];
            if(d[e.to] > d[v] + e.cost) {
                d[e.to] = d[v] + e.cost;
                que.push(P(d[e.to], e.to));
            }
        }
    } 
}

int main() {
    cin >> V;
    rep(i,V - 1) {
        int a, b, c;
        cin >> a >> b >> c;
        a--; b--;
        edge e = {b, c};
        G[a].pub(e);
        edge f = {a, c};
        G[b].pub(f);
    }
    ll ans = 0;
    rep(i,V){
        dijkstra(i);
        repk(j,i+1,V) ans += d[j];
    }
    cout << 2 * ans << endl;
}
0