fork download
copy 
  1. // TranThienPhuc2657
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. #define file "TASK"
  5. #define TIME 1.0 * clock() / CLOCKS_PER_SEC
  6. #define ll long long
  7. #define pb push_back
  8. #define fi first
  9. #define se second
  10. #define pii pair <int, int>
  11. #define pll pair <ll, ll>
  12. #define Sz(x) ((int) (x).size())
  13. #define getBit(mask, i) (((mask) >> (i)) & 1)
  14. template <typename T1, typename T2> bool mini(T1 &A, T2 B) {if (A > B) A = B; else return 0; return 1;}
  15. template <typename T1, typename T2> bool maxi(T1 &A, T2 B) {if (A < B) A = B; else return 0; return 1;}
  16. const int inf = 2e9 + 7;
  17. const ll linf = 1e18l + 7;
  18. const int mod = 1e9 + 7;
  19. const int N = 5e4 + 5;
  20.  
  21. int n, m, c, r, k;
  22. vector <pii> adj[N];
  23. vector <int> vis[N];
  24. struct Dij {
  25.     int u, du, root;
  26.  
  27.     bool operator < (const Dij &ot) const {
  28.         return du > ot.du;
  29.     }
  30. };
  31. vector <int> res;
  32.  
  33. // inp
  34. void inp() {
  35.     cin >> n >> m >> c >> r >> k;
  36.     for (int i = 1; i <= m; i++) {
  37.         int u, v, w; cin >> u >> v >> w;
  38.         adj[u].pb({v, w});
  39.         adj[v].pb({u, w});
  40.     }
  41. }
  42.  
  43. // init
  44. void init() {
  45.  
  46. }
  47.  
  48. // proc
  49. void proc() {
  50.     priority_queue <Dij> pq;
  51.  
  52.     for (int u = 1; u <= c; u++) pq.push({u, 0, u});
  53.  
  54.     while (!pq.empty()) {
  55.         int u = pq.top().u, du = pq.top().du, root = pq.top().root; pq.pop();
  56.  
  57.         if (Sz(vis[u]) >= k) continue;
  58.         bool hasSeen = false;
  59.         for (int i: vis[u]) if (i == root) {
  60.             hasSeen = true;
  61.             break;
  62.         }
  63.         if (hasSeen) continue;
  64.  
  65.         vis[u].pb(root);
  66.         for (pii e: adj[u]) {
  67.             int v = e.fi, w = e.se;
  68.             if (du + w > r or Sz(vis[v]) >= k) continue;
  69.             bool hasSeen = false;
  70.             for (int i: vis[v]) if (i == root) {
  71.                 hasSeen = true;
  72.                 break;
  73.             }
  74.             if (hasSeen) continue;
  75.             pq.push({v, du + w, root});
  76.         }
  77.     }
  78.  
  79.     for (int u = c + 1; u <= n; u++) if (Sz(vis[u]) == k) res.pb(u);
  80.  
  81.     cout << Sz(res) << "\n";
  82.     for (int u: res) cout << u << "\n";
  83. }
  84.  
  85. signed main() {
  86.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  87.     if (fopen(file".inp", "r")) {
  88.         freopen(file".inp", "r", stdin);
  89.         freopen(file".out", "w", stdout);
  90.     }
  91.  
  92.     inp();
  93.     init();
  94.     proc();
  95.     cerr << "Time elapsed: " << TIME << "s.\n";
  96.     return 0;
  97. }
  98.  
Success #stdin #stdout #stderr 0.01s 6092KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
stderr
copy 
Time elapsed: 0.009008s.
https://ideone.com/ThYhNl
language:
C++14 (clang 8.0)
created:
12 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!