MathQ_

Untitled

Jan 20th, 2021
115
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.78 KB | None | 0 0
  1. #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
  2. #pragma GCC optimize 03
  3. #pragma GCC optimize("unroll-loops")
  4.  
  5. #include <iostream>
  6. #include <algorithm>
  7. #include <iterator>
  8. #include <iomanip>
  9. #include <cmath>
  10. #include <ctime>
  11. #include <vector>
  12. #include <deque>
  13. #include <queue>
  14. #include <set>
  15. #include <map>
  16. #include <stack>
  17. #include <string>
  18. #include <random>
  19. #include <numeric>
  20. #include <unordered_set>
  21.  
  22. typedef long long ll;
  23. typedef long double lb;
  24.  
  25. #define fast ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  26. #define file_in freopen("input.txt", "r", stdin);
  27. #define file_in_out freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
  28. #define pii pair<int, int>
  29. #define all(x) (x).begin(), (x).end()
  30. #define fi first
  31. #define se second
  32.  
  33. using namespace std;
  34.  
  35. template<typename T>
  36. istream& operator>>(istream &in, vector<T> &v) {
  37.     for (auto &it : v) {
  38.         in >> it;
  39.     }
  40.     return in;
  41. }
  42.  
  43. template<typename T>
  44. ostream& operator<<(ostream &out, vector<T> &v) {
  45.     if (!v.empty()) {
  46.         out << v.front();
  47.         for (int i = 1; i < v.size(); ++i) {
  48.             out << " " << v[i];
  49.         }
  50.     }
  51.     return out;
  52. }
  53.  
  54. template<typename T>
  55. istream& operator>>(istream &in, pair<T, T> &v) {
  56.     in >> v.x >> v.y;
  57.     return in;
  58. }
  59.  
  60. template<typename T>
  61. ostream& operator<<(ostream &out, pair<T, T> &v) {
  62.     out << v.x << " " << v.y;
  63.     return out;
  64. }
  65.  
  66. const int INF = 2e9;
  67.  
  68. int s;
  69. vector<char> spec;
  70. vector<int> dist;
  71. vector<vector<pair<int, int>>> g;
  72.  
  73. void bfs(int st) {
  74.     queue<pair<int, int>> q;
  75.     q.push({st, s});
  76.  
  77.     while (!q.empty()) {
  78.         int v = q.front().fi;
  79.         int now = q.front().se;
  80.         q.pop();
  81.         if (spec[v] == 1) {
  82.             dist[v] = 0;
  83.             now = s;
  84.         }
  85.         for (auto uu : g[v]) {
  86.             int u = uu.fi, w = uu.se;
  87.             if (dist[u] > dist[v] + w && now >= w) {
  88.                 dist[u] = dist[v] + w;
  89.                 q.push({u, now - w});
  90.             }
  91.         }
  92.     }
  93. }
  94.  
  95. int main() {
  96.     fast
  97.     // file_in
  98.     // file_in_out
  99.    
  100.     // int start = clock();
  101.     int n, m, k;
  102.     cin >> n >> m >> k >> s;
  103.     g.resize(n); spec.resize(n, 0); dist.resize(n, INF);
  104.     int v, u, w;
  105.     for (int i = 0; i < m; ++i) {
  106.         cin >> v >> u >> w;
  107.         --v; --u;
  108.         g[v].push_back({u, w});
  109.         g[u].push_back({v, w});
  110.     }
  111.     for (int i = 0; i < k; ++i) {
  112.         cin >> v; --v;
  113.         spec[v] = 1;
  114.     }
  115.     bfs(0);
  116.     int cnt = 0;
  117.     for (int i = 0; i < n; ++i) {
  118.         if (dist[i] != INF) {
  119.             ++cnt;
  120.         }
  121.     }
  122.     cout << cnt << '\n';
  123.     for (int i = 0; i < n; ++i) {
  124.         if (dist[i] != INF) {
  125.             cout << i + 1 << ' ';
  126.         }
  127.     }
  128.     return 0;
  129. }
Advertisement
Add Comment
Please, Sign In to add comment