fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. typedef pair <ll, int> pli;
  5. typedef pair <int, int> pii;
  6. typedef pair <ll, ll> pll;
  7. #define fr first
  8. #define sc second
  9. #define sz(x) int(x.size())
  10. #define all(x) x.begin(), x.end()
  11. #define lb lower_bound
  12. #define ub upper_bound
  13. #define ins insert
  14. #define pb push_back
  15. #define mp(a, b) make_pair(a, b)
  16. #define ppb pop_back()
  17. #define mint ModInt
  18. const int mod = 998244353;
  19. const int N = 2e5 + 2, inf = 1e9;
  20. const ll oo = 1e18;
  21. vector <pii> g[N];
  22. vector <int> gr[N], o;
  23. bool u[N];
  24. ll d[N];
  25. int pr[N], a[N], b[N], c[N], n, m, k, s;
  26. vector <int> arr;
  27. void dfs(int v){
  28. 	u[v] = 1;
  29. 	o.pb(v);
  30. 	for(auto to : gr[v]){
  31. 		if(!u[to])dfs(to);
  32. 	}
  33. }
  34. void regular_dj(vector <int> list){
  35. 	set <pli> st;
  36. 	fill(d, d + n + 1, oo);
  37. 	for(auto to : list){
  38. 		st.ins({0, to});
  39. 		d[to] = 0;
  40. 		pr[to] = to;
  41. 	}
  42. 	//return;
  43. 	while(!st.empty()){
  44. 		int v = st.begin() -> sc;
  45. 		st.erase(st.begin());
  46. 		//cerr << v << endl;
  47. 		for(auto it : g[v]){
  48. 			int to = it.fr, w = it.sc;
  49. 			if(d[to] > d[v] + w){
  50. 				st.erase({d[to], to});
  51. 				d[to] = d[v] + w;
  52. 				pr[to] = pr[v];
  53. 				st.ins({d[to], to});
  54. 			}
  55. 		}
  56. 	}
  57. }
  58.  
  59. void solve(){
  60. 	cin >> n >> m >> k >> s;
  61. 	for(int i = 1;i <= m; ++ i){
  62. 		cin >> a[i] >> b[i] >> c[i];
  63. 		g[a[i]].pb({b[i], c[i]});
  64. 		g[b[i]].pb({a[i], c[i]});
  65. 	}
  66. 	//return;
  67. 	for(int i = 1;i <= k; ++ i){
  68. 		int x;
  69. 		cin >> x;
  70. 		o.pb(x);
  71. 	}
  72. 	vector <int> ans;
  73. 	//return;
  74. 	regular_dj(o);
  75. 	o.clear();
  76. 	for(int i = 1;i <= m; ++ i){
  77. 		if(pr[a[i]] != pr[b[i]] && d[a[i]] + d[b[i]] + c[i] <= s){
  78. 			int v = pr[a[i]], to = pr[b[i]];
  79. 			gr[v].pb(to);
  80. 			gr[to].pb(v);
  81. 		}
  82. 	}
  83. 	dfs(1);
  84. 	regular_dj(o);
  85. 	for(int i = 1;i <= n; ++ i){
  86. 		if(d[i] <= s){
  87. 			ans.pb(i);
  88. 		}
  89. 	}
  90. 	cout << sz(ans) << endl;
  91. 	for(auto to : ans){
  92. 		cout << to << " ";
  93. 	}
  94. }
  95.  
  96. int main(){
  97. 	//freopen("input.txt", "r", stdin);
  98. 	//freopen("output.txt", "w", stdout);
  99. 	ios_base::sync_with_stdio(0);
  100. 	int T = 1;
  101. 	//cin >> T;
  102. 	while(T--){
  103. 		solve();
  104. 	}
  105. 	return 0;
  106. }
  107.  
Success #stdin #stdout 0.01s 16752KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/QQTX5o
language:
C++14 (gcc 8.3)
created:
9 hours ago
visibility:
public

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!