fork download 
  1.  
  2. #include<bits/stdc++.h>
  3. #include<ext/pb_ds/assoc_container.hpp> 
  4. #include<ext/pb_ds/tree_policy.hpp> 
  5. using namespace std;
  6. void __print(int x) {cerr << x;}
  7. void __print(long x) {cerr << x;}
  8. void __print(long long x) {cerr << x;}
  9. void __print(unsigned x) {cerr << x;}
  10. void __print(unsigned long x) {cerr << x;}
  11. void __print(unsigned long long x) {cerr << x;}
  12. void __print(float x) {cerr << x;}
  13. void __print(double x) {cerr << x;}
  14. void __print(long double x) {cerr << x;}
  15. void __print(char x) {cerr << '\'' << x << '\'';}
  16. void __print(const char *x) {cerr << '\"' << x << '\"';}
  17. void __print(const string &x) {cerr << '\"' << x << '\"';}
  18. void __print(bool x) {cerr << (x ? "true" : "false");}
  19.  
  20. template<typename T, typename V>
  21. void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
  22. template<typename T>
  23. void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
  24. void _print() {cerr << "]\n";}
  25. template <typename T, typename... V>
  26. void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
  27. #ifndef ONLINE_JUDGE
  28. #define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
  29. #else
  30. #define debug(x...)
  31. #endif
  32.  
  33. #define ll long long int
  34. #define md 1000000007
  35. #define vi vector<int> 
  36. #define mx(a,b,c,d) max(a, max(b, max(c,d)))
  37. #define MP make_pair
  38. #define pb push_back
  39. #define ppb pop_back
  40.  
  41.  
  42. ll modular_exponentiation(ll base, ll exponent)
  43. { 
  44. 	ll res=1;
  45. 	while(exponent>0)
  46. 	{
  47. 		if(exponent%2==0){
  48. 			base=(base*base)%md;
  49. 			exponent/=2;
  50. 		}
  51. 		else{
  52. 			res=(res*base)%md;
  53. 			exponent--;
  54.  
  55. 		}
  56. 	}
  57. 		return res;	
  58. }
  59.  
  60. const ll S=1e7+1;
  61. bool arr1[(long long)S] ;
  62.  
  63. void sieve(){
  64.  
  65.  
  66. 	memset(arr1, true, sizeof(arr1));
  67.  
  68.  
  69. 	for(int i=2; i*i<=(long long)S; i++){
  70.  
  71. 		if(arr1[i]==true){
  72.  
  73.  
  74.  
  75. 			for(int j=i*i; j<=(long long)1e7; j+=i){
  76.  
  77. 				arr1[j]=false;
  78.  
  79. 			}
  80. 		}
  81. 	}
  82.  
  83. 	//for (int i = 2; i <= 1e6; i++)
  84.         //if (arr1[i]==true)
  85.             //cout << "YES" << " ";
  86.  
  87.  
  88. }
  89. auto pos(vector<ll> arr){
  90.  
  91. 	for(int i=0; i<(int)arr.size(); i++){
  92. 		if(arr[i]>=0){
  93.  
  94. 			return true;
  95. 		}
  96.  
  97. 	}
  98. 	return false;
  99.  
  100. }
  101. auto even(int x){
  102.  
  103. 	return x%2==0;
  104.  
  105. }
  106. //struct Edge{
  107.  
  108. 	//ll src, des, wt;
  109.  
  110. //};
  111.  
  112.  
  113. ll m,n;
  114. vector<tuple<ll, ll ,ll> > edges;
  115. void BellmanFord(){
  116.  
  117. 	vector<ll> parents;
  118. 	vector<ll> value;
  119.  
  120. 	parents.resize(n, -1);
  121. 	value.resize(n, md);
  122. 	//edges.resize(10000000);
  123.  
  124. 	value[0]=0;
  125.  
  126. 	parents[0]=-1;
  127.  
  128.  
  129.  
  130. 	for(int i=0; i<n-1; i++){
  131.  
  132. 		for(auto& edge: edges){
  133.  
  134. 			ll u,v,wt;
  135.  
  136. 			tie(u,v,wt)=edge;
  137. 			debug(u,v,wt);
  138. 			//ll u=edges[j].src;
  139. 			//ll v=edges[j].des;
  140. 			//ll wt=edges[j].wt;
  141. 			if(value[u]!=md and value[u]+wt<value[v]){
  142.  
  143. 				value[v]=value[u]+wt;
  144. 				parents[v]=u;
  145.  
  146. 			}
  147. 		}
  148.  
  149. 	}
  150.  
  151. 	cout<<endl;
  152. 	debug(parents);
  153. 	debug(value);
  154.  
  155. 	//for(auto& it:value)cout<<it<<" ";
  156. }
  157.  
  158.  
  159. void solve()
  160. {		
  161.  
  162. 	cin>>n>>m;
  163.  
  164. 	//vector<Edge> edges(m);
  165.  
  166. 			for(int i=0; i<m; i++){
  167.  
  168. 				ll src,des,wt;
  169. 				cin>>src>>des>>wt;
  170. 				edges.pb({src,des,wt});
  171.  
  172. 				//src--, des--, wt--;
  173. 				//edges[i].src=src;
  174. 				//edges[i].des=des;
  175. 				//edges[i].wt=wt;
  176.  
  177. 			}
  178. 	//ll a,b,c;
  179. 	//tie(a,b,c);
  180. 	BellmanFord();
  181.  
  182.  
  183. }
  184.  
  185. int main() {
  186.  
  187.  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  188.  
  189. //int T;
  190.     //cin>>T;
  191.     sieve();
  192.    // while (T--){
  193. 		solve();
  194. 		cerr << "time taken : " << (float)clock() / CLOCKS_PER_SEC << " secs" << endl;
  195.  
  196. 		//}
  197.  
  198.  
  199.  
  200. }
  201.  
  202.  
  203.  
Runtime error #stdin #stdout 0.05s 13168KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/PHT2kj
language:
C++ (gcc 8.3)
created:
4 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!