fork download 
  1. //teja349
  2. #include <bits/stdc++.h>
  3. #include <vector>
  4. #include <set>
  5. #include <map>
  6. #include <string>
  7. #include <cstdio>
  8. #include <cstdlib>
  9. #include <climits>
  10. #include <utility>
  11. #include <algorithm>
  12. #include <cmath>
  13. #include <queue>
  14. #include <stack>
  15. #include <iomanip>
  16. #include <ext/pb_ds/assoc_container.hpp>
  17. #include <ext/pb_ds/tree_policy.hpp> 
  18. //setbase - cout << setbase (16); cout << 100 << endl; Prints 64
  19. //setfill -   cout << setfill ('x') << setw (5); cout << 77 << endl; prints xxx77
  20. //setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
  21. //cout.precision(x)  cout<<fixed<<val;  // prints x digits after decimal in val
  22.  
  23. using namespace std;
  24. using namespace __gnu_pbds;
  25.  
  26. #define f(i,a,b) for(i=a;i<b;i++)
  27. #define rep(i,n) f(i,0,n)
  28. #define fd(i,a,b) for(i=a;i>=b;i--)
  29. #define pb push_back
  30. #define mp make_pair
  31. #define vi vector< int >
  32. #define vl vector< ll >
  33. #define ss second
  34. #define ff first
  35. #define ll long long
  36. #define pii pair< int,int >
  37. #define pll pair< ll,ll >
  38. #define sz(a) a.size()
  39. #define inf (1000*1000*1000+5)
  40. #define all(a) a.begin(),a.end()
  41. #define tri pair<int,pii>
  42. #define vii vector<pii>
  43. #define vll vector<pll>
  44. #define viii vector<tri>
  45. #define mod (1000*1000*1000+7)
  46. #define pqueue priority_queue< int >
  47. #define pdqueue priority_queue< int,vi ,greater< int > >
  48. #define flush fflush(stdout) 
  49. #define primeDEN 727999983
  50. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  51.  
  52. // find_by_order()  // order_of_key
  53. typedef tree<
  54. int,
  55. null_type,
  56. less<int>,
  57. rb_tree_tag,
  58. tree_order_statistics_node_update>
  59. ordered_set;
  60.  
  61. #define int ll
  62.  
  63. struct Edge{
  64. 	int u,v,c;
  65. };
  66. Edge ed[123456];
  67. int dist[123456],visit[123456];
  68.  
  69. vector<vi> adj(123456),rev(123456);
  70.  
  71. int dfs(int cur){
  72. 	visit[cur]=1;
  73. 	int i;
  74. 	rep(i,adj[cur].size()){
  75. 		if(!visit[adj[cur][i]]){
  76. 			dfs(adj[cur][i]);
  77. 		}
  78. 	}
  79. 	return 0;
  80. }
  81.  
  82. int revdfs(int cur){
  83. 	int i;
  84. 	visit[cur]=1;
  85. 	rep(i,rev[cur].size()){
  86. 		if(!visit[rev[cur][i]]){
  87. 			revdfs(rev[cur][i]);
  88. 		}
  89. 	}
  90. 	return 0;
  91. }
  92.  
  93. main(){
  94.     std::ios::sync_with_stdio(false); cin.tie(NULL);
  95. 	int tt;
  96. 	cin>>tt;
  97. 	while(tt--){
  98. 		int n,m;
  99. 		cin>>n>>m;
  100. 		int i,j;
  101. 		int t,u,v,c;
  102. 		ll iinf = inf;
  103. 		iinf*=inf;
  104. 		rep(i,n){
  105. 			adj[i].clear();
  106. 			rev[i].clear();
  107. 		}
  108. 		rep(i,m){
  109. 			cin>>t>>u>>v>>c;
  110. 			u--;
  111. 			v--;
  112. 			if(t==1){
  113. 				ed[i].u=u;
  114. 				ed[i].v=v;
  115. 				ed[i].c=-1*c;
  116. 			}
  117. 			else{
  118. 				ed[i].u=v;
  119. 				ed[i].v=u;
  120. 				ed[i].c=c-1;
  121. 			}
  122. 		}
  123. 		rep(i,n){
  124. 			dist[i]=iinf;
  125. 		}
  126. 		dist[0]=0;
  127. 		rep(i,n+2){
  128. 			rep(j,m){
  129. 				u=ed[j].u;
  130. 				v=ed[j].v;
  131. 				c=ed[j].c;
  132. 				if(dist[v]>dist[u]+c){
  133. 					dist[v]=dist[u]+c;
  134. 				}
  135. 			}
  136. 		}
  137. 		int bad=0;
  138. 		rep(j,m){
  139. 			u=ed[j].u;
  140. 			v=ed[j].v;
  141. 			c=ed[j].c;
  142. 			if(dist[v]>dist[u]+c){
  143. 				bad=1;
  144. 			}
  145. 		}
  146. 		if(bad){
  147. 			cout<<"NO"<<endl;
  148. 			continue;
  149. 		}
  150. 		rep(i,m){
  151. 			u=ed[i].u;
  152. 			v=ed[i].v;
  153. 			c=ed[i].c;
  154. 			if(dist[u]==iinf)
  155. 				continue;
  156. 			if(dist[v]==dist[u]+c){
  157. 				adj[u].pb(v);
  158. 				rev[v].pb(u);
  159. 			}
  160. 		}
  161. 		rep(i,n){
  162. 			visit[i]=0;
  163. 		}
  164. 		dfs(0);
  165.  
  166. 		rep(i,n){
  167. 			if(visit[i]==0)
  168. 				bad=1;
  169. 		}
  170. 		rep(i,n){
  171. 			visit[i]=0;
  172. 		}
  173. 		revdfs(0);
  174.  
  175. 		rep(i,n){
  176. 			if(visit[i]==0)
  177. 				bad=1;
  178. 		}
  179. 		if(bad){
  180. 			cout<<"NO"<<endl;
  181. 			continue;
  182. 		}
  183. 		else{
  184. 			cout<<"YES"<<endl;
  185. 		}
  186. 		rep(i,n){
  187. 			cout<<dist[i]<<" ";
  188. 		}
  189. 		cout<<endl;
  190.  
  191.  
  192.  
  193. 	}
  194.     return 0;   
  195. }
Runtime error #stdin #stdout 0s 25856KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/cWZYmk
language:
C++14 (gcc 8.3)
created:
6 years 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!