fork download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <string>
  4. #include <vector>
  5. #include <assert.h>
  6. using namespace std;
  7.  
  8.  
  9.  
  10. long long readInt(long long l,long long r,char endd){
  11. 	long long x=0;
  12. 	int cnt=0;
  13. 	int fi=-1;
  14. 	bool is_neg=false;
  15. 	while(true){
  16. 		char g=getchar();
  17. 		if(g=='-'){
  18. 			assert(fi==-1);
  19. 			is_neg=true;
  20. 			continue;
  21. 		}
  22. 		if('0'<=g && g<='9'){
  23. 			x*=10;
  24. 			x+=g-'0';
  25. 			if(cnt==0){
  26. 				fi=g-'0';
  27. 			}
  28. 			cnt++;
  29. 			assert(fi!=0 || cnt==1);
  30. 			assert(fi!=0 || is_neg==false);
  31.  
  32. 			assert(!(cnt>19 || ( cnt==19 && fi>1) ));
  33. 		} else if(g==endd){
  34. 			assert(cnt>0);
  35. 			if(is_neg){
  36. 				x= -x;
  37. 			}
  38. 			if(!(l<=x && x<=r)){
  39. 				cerr<<l << " "<<r<<" "<<x<<endl;
  40. 			}
  41. 			assert(l<=x && x<=r);
  42. 			return x;
  43. 		} else {
  44. 			assert(false);
  45. 		}
  46. 	}
  47. }
  48. string readString(int l,int r,char endd){
  49. 	string ret="";
  50. 	int cnt=0;
  51. 	while(true){
  52. 		char g=getchar();
  53. 		assert(g!=-1);
  54. 		if(g==endd){
  55. 			break;
  56. 		}
  57. 		cnt++;
  58. 		ret+=g;
  59. 	}
  60. 	assert(l<=cnt && cnt<=r);
  61. 	return ret;
  62. }
  63. long long readIntSp(long long l,long long r){
  64. 	return readInt(l,r,' ');
  65. }
  66. long long readIntLn(long long l,long long r){
  67. 	return readInt(l,r,'\n');
  68. }
  69. string readStringLn(int l,int r){
  70. 	return readString(l,r,'\n');
  71. }
  72. string readStringSp(int l,int r){
  73. 	return readString(l,r,' ');
  74. }
  75.  
  76.  
  77. struct edge{
  78. 	int s,e,v;
  79. };
  80.  
  81.  
  82. edge list[5555];
  83. int n,m;
  84. int T;
  85. int sm_n=0;
  86. int sm_m=0;
  87.  
  88. long long dist[1010];
  89.  
  90. vector<int> adj[1010];
  91. bool vis[1010];
  92.  
  93. void dfs(int nd){
  94. 	vis[nd]=true;
  95. 	for(int j=0;j<adj[nd].size();j++){
  96. 		int ch=adj[nd][j];
  97. 		if(vis[ch])continue;
  98. 		dfs(ch);
  99. 	}
  100. }
  101.  
  102. int main(){
  103. 	//freopen("00.txt","r",stdin);
  104. 	//freopen("00o.txt","w",stdout);
  105. 	T=readIntLn(1,1000);
  106. 	while(T--){
  107. 		cerr<<1;
  108. 		n=readIntSp(2,1000);
  109. 		m=readIntLn(1,5000);
  110.  
  111. 		sm_n+=n;
  112. 		sm_m+= m;
  113. 		assert(sm_n<=10000);
  114. 		assert(sm_m<=50000);
  115. 		for(int i=1;i<=n;i++){
  116. 			dist[i]= 0;
  117. 			adj[i].clear();
  118. 		}
  119. 		for(int i=0;i<m;i++){
  120. 			int t,u,v,c;
  121. 			t=readIntSp(1,2);
  122. 			u=readIntSp(1,n);
  123. 			v=readIntSp(1,n);
  124. 			assert(u!=v);
  125. 			c=readIntLn(1,1000000000);
  126. 			if(t==1){
  127. 				list[i].s = u;
  128. 				list[i].e = v;
  129. 				list[i].v = -c;
  130. 			} else {
  131. 				list[i].s = v;
  132. 				list[i].e = u;
  133. 				list[i].v = c-1;
  134. 			}
  135. 		}
  136. 		for(int i=0;i<n;i++){
  137. 			for(int j=0;j<m;j++){
  138. 				dist[list[j].e] = min(dist[list[j].e],dist[list[j].s] + list[j].v);
  139. 			}
  140. 		}
  141. 		bool ok=true;
  142. 		for(int j=0;j<m;j++){
  143. 			if(dist[list[j].e] > dist[list[j].s] + list[j].v){
  144. 				ok=false;
  145. 			}
  146. 		}
  147. 		if(!ok){
  148. 			cout<<"NO"<<endl;
  149. 			continue;
  150. 		}
  151. 		for(int j=0;j<m;j++){
  152. 			if(dist[list[j].e] == dist[list[j].s] + list[j].v){
  153. 				adj[list[j].s].push_back(list[j].e);
  154. 			}
  155. 		}
  156. 		for(int i=1;i<=n;i++){
  157. 			for(int j=1;j<=n;j++){
  158. 				vis[j]=false;
  159. 			}
  160. 			dfs(i);
  161. 			for(int j=1;j<=n;j++){
  162. 				if(!vis[j]){
  163. 					ok=false;
  164. 				}
  165. 			}
  166. 		}
  167. 		if(!ok){
  168. 			cout<<"NO"<<endl;
  169. 			continue;
  170. 		}
  171. 		cout<<"YES"<<endl;
  172. 		for(int i=n;i>=1;i--){
  173. 			dist[i] -= dist[1];
  174. 		}
  175. 		for(int i=1;i<=n;i++){
  176. 			cout<<dist[i]<< " ";
  177. 		}
  178. 		cout<<endl;
  179. 	}
  180.  
  181. 	assert(getchar()==-1);
  182. }
Runtime error #stdin #stdout #stderr 0s 15344KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
prog: prog.cpp:44: long long int readInt(long long int, long long int, char): Assertion `false' failed.
https://ideone.com/xCdDOY
language:
C++14 (gcc 8.3)
created:
5 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!