結果
問題 |
No.1382 Travel in Mitaru city
|
ユーザー |
|
提出日時 | 2021-02-08 17:52:08 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,244 bytes |
コンパイル時間 | 1,174 ms |
コンパイル使用メモリ | 107,248 KB |
実行使用メモリ | 274,804 KB |
最終ジャッジ日時 | 2024-07-05 19:41:45 |
合計ジャッジ時間 | 6,139 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 3 TLE * 1 -- * 64 |
ソースコード
#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 b1[100010]; 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]; b1[i] = 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); } priority_queue<pair<int, int>> que; que.push(make_pair(p[s], s)); set<int> st; b[s] = true; while (!que.empty()) { int x = que.top().second; int y = que.top().first; que.pop(); for (int i = 0; i < vec[x].size(); i++) { if (y > p[vec[x][i]]) { st.insert(p[vec[x][i]]); } if (!b[vec[x][i]]) { que.push(make_pair(min(y, p[vec[x][i]]), vec[x][i])); b1[vec[x][i]] = min(y, p[vec[x][i]]); b[vec[x][i]] = true; } else if (y > b1[vec[x][i]]) { que.push(make_pair(min(y, p[vec[x][i]]), vec[x][i])); b1[vec[x][i]] = min(y, p[vec[x][i]]); } } } cout << st.size() << endl; }