結果
問題 | No.807 umg tours |
ユーザー |
|
提出日時 | 2023-06-03 12:17:42 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 612 ms / 4,000 ms |
コード長 | 3,916 bytes |
コンパイル時間 | 1,077 ms |
コンパイル使用メモリ | 83,448 KB |
実行使用メモリ | 45,720 KB |
最終ジャッジ日時 | 2024-12-29 02:42:23 |
合計ジャッジ時間 | 8,250 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 26 |
ソースコード
#include <iostream>using namespace std;#include<vector>#include<queue>// 無効グラフ, 非負重み// edgeの個数 2*10^5// node の数 10^5// スタートは全て1 , 各ノードへの最短距離 + 一つを0にした時の最短経路を求める.// 重みを0にしない時の最短経路と0にした時の経路は変わることもある.// ex) 行き 経路1 のコストが 2 + 3 ,経路2のコストが1+10の時,息は経路1 , 帰りは経路2となる.// edgeの数が10^5であり,それらについて一つを0にするようなグラフを作るとすると,// 10^5このグラフができる.// 各グラフごとに拡張点までの計算はダイクストラ法を使うと// 10^5で一度に計算できる.// ただ,それでは計算が間に合わない.// そこで,各ノードに割り振る値を2次元にする.// 一つは0を適用していない最小コスト// もう一つは,一つだけ最小のコストを適用した時のコストである.// このようにすると,そのノードから隣接ノードへの計算は// next_node = ( node[0] + edge_cost ,min (node[1]+edge_cost,node[0]+0 )// と計算できる.// これをノード間の計算コストとしてダイクストラ法を適用する.なお,この二次元のやつは2倍のノード数と見て// キューに突っ込んでしまっても問題ないと思う.つまり,平行に2層に並んだグラフ構造を思い浮かべたときに// 1層目は普通のダイクストラであり,2層目は2層目の周囲のノードからコストedge_costで接続され,さらに// 1層目の周囲のノードからedge_costで接続されているという状態となる.// こうすることで,ノードiへの往復はnode[i][0]+node[i][1]で計算できる.iは10^5個ある.// この考え方によりノードの数は2V となり,エッジの数は3Eとなる.// またおののの道は双方向であることに注意したい.// この時計算コストは, 優先度付きキュー(2分ヒープ)を使うことで (E+V)logV となり,計算可能.int main(){int n,m;cin>>n>>m;vector<long long int> cost(2*n,3*m*(1e10));priority_queue< pair<long long int,int> > q; // [cost,node_i] ただし2層目はnod_i + V とする.// q.push(), q.empty() , q.top(), q.pop()vector< vector<pair<int,long long int> > > neighbor(2*n); // nこのvectorを定義 from to cost// neighbor[i] は, <node_i,cost2node_i> の配列int a,b,c;for(int i=0;i<m;i++){cin >> a >> b >> c;if (a==b) continue; // 条件になかったので一応neighbor[a-1].push_back(make_pair(b-1,c));neighbor[b-1].push_back(make_pair(a-1,c));neighbor[a-1+n].push_back(make_pair(b-1+n,c));neighbor[b-1+n].push_back(make_pair(a-1+n,c));neighbor[a-1].push_back(make_pair(b-1+n,0));neighbor[b-1].push_back(make_pair(a-1+n,0));}cost[0]=0;// cost[n]=0; // 注意q.push(make_pair(-0,0));// priority はデフォででかい方から取り出す.めんどなので正負pair<long long int,int> t_node; //target nodepair<int,long long int> n_node; // next node from target_nodewhile(!q.empty()){t_node = q.top();q.pop();if (cost[t_node.second]<-t_node.first){continue; // 訪問済み}for(int i=0;i<neighbor[t_node.second].size();i++){n_node=neighbor[t_node.second][i];if (cost[n_node.first]> -t_node.first + n_node.second){cost[n_node.first]=-t_node.first + n_node.second;q.push(make_pair(-cost[n_node.first],n_node.first));}}}for(int i=0;i<n;i++){cout << cost[i]+min(cost[i+n],cost[i]) <<endl;}return 0;}