結果
問題 |
No.1382 Travel in Mitaru city
|
ユーザー |
|
提出日時 | 2021-02-09 06:17:53 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 64 ms / 2,000 ms |
コード長 | 1,051 bytes |
コンパイル時間 | 1,963 ms |
コンパイル使用メモリ | 174,968 KB |
実行使用メモリ | 10,524 KB |
最終ジャッジ日時 | 2024-07-06 12:12:00 |
合計ジャッジ時間 | 7,812 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 68 |
ソースコード
#include<bits/stdc++.h> using namespace std; const int MAX_N = 1e5+2; int n,m,s,t; int u0,v0; vector<int> adj[MAX_N]; int p[MAX_N]; bool used[MAX_N]; priority_queue< pair<int,int> > pq; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin>>n>>m>>s>>t; for(int i=1; i<=n; i++) { cin>>p[i]; } for(int i=0; i<m; i++) { cin>>u0>>v0; adj[u0].push_back(v0); adj[v0].push_back(u0); } int ans = 0; int val = p[s]; used[s] = true; pq.push({p[s],s}); ///cout<<endl; while(!pq.empty()) { pair<int,int> tmp = pq.top(); ///cout<<tmp.first<<" "<<tmp.second<<endl; pq.pop(); if(val > tmp.first) { val = tmp.first; ans++; } for(auto x: adj[tmp.second]) { if(used[x] == 0) { used[x] = 1; pq.push({p[x],x}); } } } if(used[t])cout<<ans<<endl; else cout<<0<<endl; }