fork download
copy 
  1. // #include<bits/stdc++.h>
  2. #include <iostream>
  3. #include <cstdio>
  4. #include <algorithm>
  5. #include <cmath>
  6. #include <vector>
  7. #include <set>
  8. #include <map>
  9. #include <unordered_set>
  10. #include <unordered_map>
  11. #include <queue>
  12. #include <string>
  13. #include <cstring>
  14. #include <random>
  15. #include <bitset>
  16. // #include <ext/pb_ds/assoc_container.hpp>
  17. // #include <ext/pb_ds/tree_policy.hpp>
  18. // using namespace __gnu_pbds;
  19. // template<class T> using oset =tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update> ;
  20. using namespace std;
  21. // #pragma GCC optimize("Ofast")
  22. // #pragma GCC target("avx,avx2,fma")
  23. // #pragma GCC optimization ("unroll-loops")
  24. typedef long long ll ;
  25. typedef pair<int,int> pii;
  26. typedef pair<ll,ll> pll;
  27. #define CS custom_hash
  28. #define vt vector 
  29. #define F first
  30. #define S second
  31. #define pb push_back
  32. #define em emplace_back
  33. #define stoi stoll
  34. #define all(v) (v).begin(),(v).end()                                            
  35. #define mems(x, y) memset(x, y, sizeof(x))
  36. #define sz(x) (int)(x).size()
  37. #define ar array
  38. #define endl "\n" 
  39. #define PI acos(-1) 
  40. #define umap unordered_map
  41. #define gmap gp_hash_table
  42. #define ld long double 
  43. #define seb(n) __builtin_popcountll(n) 
  44. #define LB lower_bound  
  45. #define UB upper_bound 
  46. // debugger credits: https://c...content-available-to-author-only...s.com/blog/entry/68809 
  47. void __print(int x) {cerr << x;}
  48. void __print(long x) {cerr << x;}
  49. void __print(long long x) {cerr << x;}
  50. void __print(unsigned x) {cerr << x;}
  51. void __print(unsigned long x) {cerr << x;}
  52. void __print(unsigned long long x) {cerr << x;}
  53. void __print(float x) {cerr << x;}
  54. void __print(double x) {cerr << x;}
  55. void __print(long double x) {cerr << x;}
  56. void __print(char x) {cerr << '\'' << x << '\'';}
  57. void __print(const char *x) {cerr << '\"' << x << '\"';}
  58. void __print(const string &x) {cerr << '\"' << x << '\"';}
  59. void __print(bool x) {cerr << (x ? "true" : "false");}
  60. template<typename T, typename V>
  61. void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
  62. template<typename T>
  63. void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
  64. void _print() {cerr << "]\n";}
  65. template <typename T, typename... V>
  66. void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
  67. template <typename T, typename V>
  68. void mdebug(map<T,vector<V>>m){
  69.   for(auto x:m){
  70.     cerr << x.first << " : [ " ;
  71.     for(auto c:x.second)
  72.       cerr << c << " ";
  73.     cerr << "]"<<'\n' ;
  74.   }
  75. }
  76. #ifndef ONLINE_JUDGE
  77. #define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
  78. #else
  79. #define debug(x...)
  80. #endif
  81. //#pragma GCC optimize "trapv"
  82. //template credits :William Lin(tmwilliamlin168)
  83. #define F_OR(i, a, b, s) for (int i = (a); ((s) > 0 ? i < (b) : i > (b)); i += (s))
  84. #define F_OR1(e) F_OR(i, 0, e, 1)
  85. #define F_OR2(i, e) F_OR(i, 0, e, 1)
  86. #define F_OR3(i, b, e) F_OR(i, b, e, 1)
  87. #define F_OR4(i, b, e, s) F_OR(i, b, e, s)
  88. #define GET5(a, b, c, d, e, ...) e
  89. #define F_ORC(...) GET5(__VA_ARGS__, F_OR4, F_OR3, F_OR2, F_OR1)
  90. #define FOR(...) F_ORC(__VA_ARGS__)(__VA_ARGS__)
  91. #define EACH(x, a) for (auto& x: a)
  92. template<class T> bool umin(T& a, const T& b) {
  93. 	return b<a?a=b, 1:0;
  94. }
  95. template<class T> bool umax(T& a, const T& b) { 
  96. 	return a<b?a=b, 1:0;
  97. }
  98. template<class A> void read(vt<A>& v);
  99. template<class A, size_t S> void read(ar<A, S>& a);
  100. template<class T> void read(T& x) {
  101. 	cin >> x;
  102. }
  103. void read(double& d) {
  104. 	string t;
  105. 	read(t);
  106. 	d=stod(t);
  107. }
  108. void read(long double& d) {
  109. 	string t;
  110. 	read(t);
  111. 	d=stold(t);
  112. }
  113. template<class H, class... T> void read(H& h, T&... t) {
  114. 	read(h);
  115. 	read(t...);
  116. }
  117. template<class A> void read(vt<A>& x) {
  118. 	EACH(a, x)
  119. 		read(a);
  120. }
  121. template<class A, size_t S> void read(array<A, S>& x) {
  122. 	EACH(a, x)
  123. 		read(a);
  124. }
  125. string to_string(char c) {
  126. 	return string(1, c);
  127. }
  128. string to_string(bool b) {
  129. 	return b?"true":"false";
  130. }
  131. string to_string(const char* s) {
  132. 	return string(s);
  133. }
  134. string to_string(string s) {
  135. 	return s;
  136. }
  137. string to_string(vt<bool> v) {
  138. 	string res;
  139. 	FOR(sz(v))
  140. 		res+=char('0'+v[i]);
  141. 	return res;
  142. }
  143.  
  144. template<size_t S> string to_string(bitset<S> b) {
  145. 	string res;
  146. 	FOR(S)
  147. 		res+=char('0'+b[i]);
  148. 	return res;
  149. }
  150. template<class T> string to_string(T v) {
  151.     bool f=1;
  152.     string res;
  153.     EACH(x, v) {
  154. 		if(!f)
  155. 			res+=' ';
  156. 		f=0;
  157. 		res+=to_string(x);
  158. 	}
  159.     return res;
  160. }
  161.  
  162. template<class A> void pff(A x) {
  163. 	cout << to_string(x);
  164. }
  165. template<class H, class... T> void pff(const H& h, const T&... t) { 
  166. 	pff(h);
  167. 	pff(t...);
  168. }
  169. void print() {
  170. 	pff("\n");
  171. }
  172. template<class H, class... T> void print(const H& h, const T&... t) { 
  173. 	pff(h);
  174. 	if(sizeof...(t))
  175. 		pff(' ');
  176. 	print(t...);
  177. }
  178. struct PH{
  179.   size_t operator()(const pair<int,int>&x)const{
  180.     size_t ans=0;
  181.     for(int i=0;i<x.first;i++)
  182.       ans+=x.second;
  183.     return ans;
  184.   }
  185. };
  186. // struct custom_hash {
  187. //   static uint64_t splitmix64(uint64_t x) {
  188. //     // http://x...content-available-to-author-only...i.it/splitmix64.c
  189. //     x += 0x9e3779b97f4a7c15;
  190. //     x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
  191. //     x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
  192. //     return x ^ (x >> 31);
  193. //   }
  194. //   size_t operator()(uint64_t x) const {
  195. //     static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
  196. //     return splitmix64(x + FIXED_RANDOM);
  197. //   }
  198. // };
  199. // void DBG() {
  200. // 	cerr << "]" << endl;
  201. // }
  202. // template<class H, class... T> void DBG(H h, T... t) {
  203. // 	cerr << to_string(h);
  204. // 	if(sizeof...(t))
  205. // 		cerr << ", ";
  206. // 	DBG(t...);
  207. // }
  208. // // #ifdef _DEBUG
  209. // #define dbg(...) cerr << "LINE(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
  210. // // #else
  211. // // #define dbg(...) 0
  212. // // #endif
  213.  
  214. template<class T> void offset(ll o, T& x) {
  215. 	x+=o;
  216. }
  217. template<class T> void offset(ll o, vt<T>& x) {
  218. 	EACH(a, x)
  219. 		offset(o, a);
  220. }
  221. template<class T, size_t S> void offset(ll o, ar<T, S>& x) {
  222. 	EACH(a, x)
  223. 		offset(o, a);
  224. }
  225. template<class T> void fk(T a) { 
  226.   print(a) ;
  227.   exit(0) ;
  228. }
  229. #define pf(n) return print(n)
  230. #define int ll 
  231. long const M=1e9+7;
  232. const ll INF =1e18;
  233. // order_of_key (k) : Number of items strictly smaller than k .
  234. // find_by_order(k) : K-th element in a set (counting from zero).
  235. //Syntax to create a min heap for priority queue
  236. // priority_queue <T, vector<T>, greater<T>>pq ;
  237.  
  238. //make sure to clear the adjacency list for every test case 
  239. // check mxN size 
  240. //check if numbers are big use powl,sqrtl,builtin_popcountll()...... 
  241. const int mxN=2e5+10,di[4]={1,0,-1,0},dj[4]={0,-1,0,1};
  242. int n,m ,a[mxN],b[mxN],c[mxN],d[mxN],p;
  243. vt<ar<int,2>>adj[mxN] ;
  244. int k;
  245. vt<int>dp[20] ;
  246. void dijktras(int s){
  247.   priority_queue<ar<int,2>,vector<ar<int,2>>,greater<ar<int,2>>> pq ;
  248.   pq.push({0,s}) ;
  249.   memset(d,0x3f,sizeof(d)) ;d[s]=0 ;
  250.   while(pq.size()){
  251.     ar<int,2> u= pq.top() ;
  252.     pq.pop() ;
  253.     if(u[0]>d[u[1]])
  254.       continue ;
  255.     for(ar<int,2> v:adj[u[1]]){
  256.       if(u[0]+v[0]<d[v[1]]){
  257.         d[v[1]]=u[0]+v[0] ;
  258.         pq.push({d[v[1]],v[1]}) ;
  259.       }
  260.     }
  261.   }
  262. }
  263. int find(int P,vt<int>e){
  264.  
  265. 	EACH(x,e){
  266. 		if(x<1)
  267. 			return 1e18 ;
  268. 	}
  269. if(P==p+1)
  270. 		return 0 ;
  271. 	int mn=1e18 ;
  272. 	FOR(i,k){
  273. 		e[i]-- ;
  274. 		umin(mn,dp[P][i]+find(P+1,e)) ;
  275. 		e[i]++ ;
  276. 	}
  277. 	return mn  ;
  278.  
  279. }
  280. void solve(){		
  281. 	read(n,m) ;
  282. 	FOR(m){
  283. 		int x,y,z ;read(x,y,z) ;
  284. 		adj[x].pb({z,y}) ;
  285. 		adj[y].pb({z,x}) ;
  286. 	}
  287. 	read(k) ;
  288. 	FOR(i,k){
  289. 		read(a[i],b[i]) ;
  290.  
  291. 	}
  292. 	read(p) ;
  293. 	FOR(i,1,p+1)
  294. 		read(c[i]) ;
  295. 	FOR(i,k){
  296. 		dijktras(a[i]) ;
  297. 		FOR(j,1,p+1)
  298. 			dp[j].pb(d[c[j]]);
  299. 	}
  300.  
  301. 	vt<int>f ;
  302. 	FOR(k)
  303. 		f.pb(b[i]) ;
  304. 	int ans = find(1,f) ;
  305. 	print(ans==1e18?-1:ans) ;
  306. 	FOR(i,20)
  307. 	  dp[i].clear() ;
  308. 	FOR(i,0,n+2)
  309. 		adj[i].clear() ;
  310. 	mems(a,0) ;
  311. 	mems(b,0) ;
  312. 	mems(c,0) ;
  313.  
  314. }
  315. signed main() {
  316.   ios_base::sync_with_stdio(false);
  317.   cin.tie(NULL);
  318.   //cout << setprecision(20) << fixed ;
  319.   int T=1;
  320. 	read(T);
  321. 	FOR(_,T){
  322. 		// pff("Case #", _+1, ": ");
  323. 		solve();
  324. 	}
  325. 	return 0;
  326. }
Success #stdin #stdout 0.01s 14636KB
comments (?)
stdin
copy 
1

10 11

2 4 2

5 6 7

4 5 1

1 2 8

3 4 3

1 3 4

6 7 6

7 9 5

8 10 2

7 8 1

9 10 7

2

5 11

6 2

5

1 3 4 8 10
stdout
copy 
36
https://ideone.com/YPpCTG
language:
C++14 (gcc 8.3)
created:
3 years 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!