結果
問題 |
No.1382 Travel in Mitaru city
|
ユーザー |
|
提出日時 | 2021-02-08 17:26:49 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,026 bytes |
コンパイル時間 | 831 ms |
コンパイル使用メモリ | 106,444 KB |
実行使用メモリ | 10,224 KB |
最終ジャッジ日時 | 2024-07-05 19:17:50 |
合計ジャッジ時間 | 7,050 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 48 WA * 20 |
ソースコード
#include <iostream> #include <string> #include <algorithm> #include <vector> #include <iomanip> #include <cmath> #include <stdio.h> #include <queue> #include <deque> #include <cstdio> #include <set> #include <map> #include <bitset> #include <stack> #include <cctype> using namespace std; vector<vector<int>> vec(100010); bool b[100010] = { false }; int p[100010]; int main() { int n, m, s, t; cin >> n >> m >> s >> t; for (int i = 1; i <= n; i++) { cin >> p[i]; } for (int i = 0; i < m; i++) { int a, b; cin >> a >> b; vec[a].emplace_back(b); vec[b].emplace_back(a); } queue<pair<int, int>> que; que.push(make_pair(s, p[s])); set<int> st; b[s] = true; while (!que.empty()) { int x = que.front().first; int y = que.front().second; que.pop(); for (int i = 0; i < vec[x].size(); i++) { if (!b[vec[x][i]]) { if (y > p[vec[x][i]]) { st.insert(p[vec[x][i]]); } que.push(make_pair(vec[x][i], min(y, p[vec[x][i]]))); b[vec[x][i]] = true; } } } cout << st.size() << endl; }