結果

問題 No.3078 Very Simple Traveling Salesman Problem
ユーザー SotaUNSotaUN
提出日時 2021-04-01 21:28:17
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 1,186 bytes
コンパイル時間 1,698 ms
コンパイル使用メモリ 176,752 KB
実行使用メモリ 10,272 KB
最終ジャッジ日時 2023-08-23 05:33:21
合計ジャッジ時間 2,659 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
5,972 KB
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

struct edge{
    ll p;//点
    ll w;//辺の重み*-1
};
vector<vector<edge> > graph(100000);
vector<ll> dis(100000);
ll v,e,r;//vは頂点,eは辺,rは始点
void dijkstra(){
  for(int i = 0;i < v;i++)dis[i] = pow(10,18);
    dis[r] = 0;
    priority_queue<pair<ll,ll> > que;//重み、頂点
    que.push(make_pair(0,r));
    while(!que.empty()){
        edge now;
        now.p = que.top().second;
        now.w = que.top().first * -1;
        que.pop();
        if(dis[now.p] < now.w)continue;
        for(int i = 0;i < (int)graph[now.p].size();i++){
            if(dis[graph[now.p][i].p] > now.w + graph[now.p][i].w){
                dis[graph[now.p][i].p] = now.w + graph[now.p][i].w;
                que.push(make_pair(dis[graph[now.p][i].p] * -1,graph[now.p][i].p));
            }
        }
    }
}


int main(){
    cin >> v >> e;
    for(int i = 0;i < e;i++){
        ll a,b,c;
        cin >> a >> b >> c;
        a--,b--;
        edge ma = {b,c};
        edge mb = {a,c};
        graph[a].push_back(ma);
        graph[b].push_back(mb);
    }
    r = 0;
    dijkstra();
    cout << dis[v - 1] * 2 << endl;
}
0