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 = 1e9 + 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. int d[N], root[N];
  24. pii dp[N][15];
  25. vector <int> res;
  26.  
  27. // inp
  28. void inp() {
  29.     cin >> n >> m >> c >> r >> k;
  30.     for (int i = 1; i <= m; i++) {
  31.         int u, v, w; cin >> u >> v >> w;
  32.         adj[u].pb({v, w});
  33.         adj[v].pb({u, w});
  34.     }
  35. }
  36.  
  37. // init
  38. void init() {
  39.  
  40. }
  41.  
  42. // proc
  43. void dijkstra() {
  44.     priority_queue <pii, vector <pii>, greater <pii>> pq;
  45.     for (int u = 1; u <= n; u++) pq.push({d[u], u});
  46.  
  47.     while (!pq.empty()) {
  48.         int u = pq.top().se, du = pq.top().fi; pq.pop();
  49.         if (du > d[u]) continue;
  50.  
  51.         for (pii e: adj[u]) {
  52.             int v = e.fi, w = e.se;
  53.  
  54.             int l = du + w;
  55.             if (l > r) l = inf;
  56.  
  57.             if (mini(d[v], l)) {
  58.                 pq.push({l, v});
  59.                 root[v] = root[u];
  60.             }
  61.         }
  62.     }
  63. }
  64.  
  65. bool notHasRoot(int u, int turn, int root) {
  66.     for (int i = 1; i < turn; i++) if (dp[u][i].se == root) return false;
  67.     return true;
  68. }
  69.  
  70. void proc() {
  71.     for (int u = 1; u <= n; u++) {
  72.         d[u] = ((u <= c) ? 0 : inf);
  73.         root[u] = u;
  74.     }
  75.     dijkstra();
  76.     for (int u = 1; u <= n; u++) dp[u][1] = {d[u], root[u]};
  77.  
  78.     for (int turn = 2; turn <= k; turn++) {
  79.         for (int u = 1; u <= n; u++) {
  80.             d[u] = inf;
  81.             root[u] = u;
  82.         }
  83.  
  84.         for (int u = 1; u <= n; u++) {
  85.             for (pii e: adj[u]) {
  86.                 int v = e.fi, w = e.se;
  87.                 for (int pre = 1; pre < turn; pre++) {
  88.                     if (notHasRoot(v, turn, dp[u][pre].se) and mini(d[v], dp[u][pre].fi + w)) {
  89.                         root[v] = dp[u][pre].se;
  90.                     }
  91.                 }
  92.             }
  93.         }
  94.  
  95.         dijkstra();
  96.  
  97.         for (int u = 1; u <= n; u++) dp[u][turn] = {d[u], root[u]};
  98.     }
  99.  
  100.     for (int u = c + 1; u <= n; u++) if (dp[u][k].fi <= r) res.pb(u);
  101.     cout << Sz(res) << "\n";
  102.     for (int u: res) cout << u << "\n";
  103. }
  104.  
  105. signed main() {
  106.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  107.     if (fopen(file".inp", "r")) {
  108.         freopen(file".inp", "r", stdin);
  109.         freopen(file".out", "w", stdout);
  110.     }
  111.  
  112.     inp();
  113.     init();
  114.     proc();
  115.     cerr << "Time elapsed: " << TIME << "s.\n";
  116.     return 0;
  117. }
  118.  
Success #stdin #stdout #stderr 0.01s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
stderr
copy 
Time elapsed: 0.006697s.
https://ideone.com/2Dky0R
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!