結果

問題 No.3087 University Coloring
コンテスト
ユーザー yuusaan
提出日時 2025-03-18 08:39:07
言語 C++23
(gcc 13.3.0 + boost 1.89.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 1,111 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,825 ms
コンパイル使用メモリ 295,216 KB
実行使用メモリ 32,612 KB
最終ジャッジ日時 2025-04-04 20:33:53
合計ジャッジ時間 13,615 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 WA * 2
other AC * 6 WA * 27
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 2e18;

int main(){
    int N,M;
    cin >> N >> M;
    vector edge(N,vector<tuple<int,ll,int>>(0));
    vector<ll> C(M,0);
    for(int i = 0; i < M; i++){
        int a,b;
        ll c;
        cin >> a >> b >> c;
        a--,b--;
        c = 1000000001ll - c;
        edge[a].push_back({b,c,i});
        edge[b].push_back({a,c,i});
        C[i] = c;
    }
    priority_queue<tuple<ll,int,ll>,vector<tuple<ll,int,ll>>,greater<tuple<ll,int,ll>>> que;
    que.push({0,0,-1});
    vector<ll> dist(N,INF);
    ll ans = 0;
    while(que.size()){
        int now,edgenumber;
        ll time;
        tie(time,now,edgenumber) = que.top();
        que.pop();
        if(time >= dist[now])continue;
        dist[now] = time;
        if(edgenumber != -1)ans += 1000000001 - C[edgenumber];
        for(auto j : edge[now]){
            int to,TEN;
            ll totime;
            tie(to,totime,TEN) = j;
            if(time + totime < dist[to])que.push({time + totime,to,TEN});
        }
    }
    cout << ans * 2 << endl;
    return 0;
}
0