結果
問題 | No.807 umg tours |
ユーザー |
|
提出日時 | 2024-04-17 17:15:50 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 314 ms / 4,000 ms |
コード長 | 1,897 bytes |
コンパイル時間 | 3,575 ms |
コンパイル使用メモリ | 237,912 KB |
実行使用メモリ | 27,876 KB |
最終ジャッジ日時 | 2024-10-09 11:23:30 |
合計ジャッジ時間 | 9,150 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 26 |
ソースコード
#pragma GCC optimize("O3")#pragma GCC optimize("Ofast")#pragma GCC optimize("unroll-loops")#pragma GCC target("avx,avx2")#include <bits/stdc++.h>#define INF 1000000001LL#define LNF 1000000000000000001LL#define MOD 1000000007LL#define MAX 502#define long long long#define all(x) x.begin(),x.end()using namespace std;//dijkstravoid dijkstra(int x, vector<vector<long>> &vis, vector<pair<long,long>> graph[]){priority_queue<pair<pair<long,long>,long>, vector<pair<pair<long,long>,long>>, greater<pair<pair<long,long>,long>>> pq;for(int i = 0; i<vis.size(); i++){for(int j = 0; j<vis[i].size(); j++)vis[i][j] = LNF;}vis[x][0] = 0;vis[x][1] = 0;pq.push(make_pair(make_pair(0,0),x));pq.push(make_pair(make_pair(0,1),x));while(!pq.empty()){long a = pq.top().first.first;long aa = pq.top().first.second;long b = pq.top().second;pq.pop();if(vis[b][aa] < a)continue;for(int i = 0; i<graph[b].size(); i++){long ai = graph[b][i].first;long bi = graph[b][i].second;if(bi+a < vis[ai][aa]){vis[ai][aa] = bi+a;pq.push(make_pair(make_pair(vis[ai][aa],aa),ai));}if(aa == 0){if(a < vis[ai][1]){vis[ai][1] = a;pq.push(make_pair(make_pair(vis[ai][1],1),ai));}}}}}int main(){ios_base::sync_with_stdio(0);cin.tie(0);int n,m;cin >> n >> m;vector<pair<long,long>> graph[n+1];for(int i = 0; i<m; i++){int a,b,c;cin >> a >> b >> c;graph[a].push_back({b,c});graph[b].push_back({a,c});}vector<vector<long>> vis(n+1,vector<long>(2));dijkstra(1,vis,graph);for(int i = 1; i<=n; i++){cout << vis[i][0]+vis[i][1] << "\n";}return 0;}