結果
問題 | No.1382 Travel in Mitaru city |
ユーザー |
👑 ![]() |
提出日時 | 2021-02-07 22:53:29 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 84 ms / 2,000 ms |
コード長 | 725 bytes |
コンパイル時間 | 2,137 ms |
コンパイル使用メモリ | 198,464 KB |
最終ジャッジ日時 | 2025-01-18 15:23:56 |
ジャッジサーバーID (参考情報) |
judge3 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 68 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:14:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 14 | scanf("%d%d%d%d",&N,&M,&S,&T); S--; T--; | ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~ main.cpp:15:17: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 15 | rep(i,N) scanf("%d",&P[i]); | ~~~~~^~~~~~~~~~~~ main.cpp:17:19: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 17 | int u,v; scanf("%d%d",&u,&v); u--; v--; | ~~~~~^~~~~~~~~~~~~~
ソースコード
#include <bits/stdc++.h>using namespace std;using LL=long long;using ULL=unsigned long long;#define rep(i,n) for(int i=0; i<(n); i++)int N,M,S,T;int P[100000];vector<int> E[100000];bool F[100000];int main(){scanf("%d%d%d%d",&N,&M,&S,&T); S--; T--;rep(i,N) scanf("%d",&P[i]);rep(i,M){int u,v; scanf("%d%d",&u,&v); u--; v--;E[u].push_back(v);E[v].push_back(u);}rep(i,N) F[i]=false;priority_queue<pair<int,int>> Q;F[S]=true; Q.push({P[S],S});int X=P[S];int Y=0;while(Q.size()){int p=Q.top().second; Q.pop();if(X>P[p]){ X=P[p]; Y++; }for(int e:E[p]){if(F[e]) continue; F[e]=true;Q.push({P[e],e});}}printf("%d\n",Y);return 0;}