fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define int int64_t
  6.  
  7. vector<vector<pair<int, int>>> g[2];
  8.  
  9. const int inf = 1e15;
  10.  
  11. vector<int> dist(int z, int M) {
  12. 	int n = g[z].size();
  13. 	vector<int> dist(n, inf), in_que(n);
  14. 	deque<int> que = {0};
  15. 	dist[0] = 0;
  16. 	while(!que.empty()) {
  17. 		M--;
  18. 		if(M < 0) {
  19. 			return {-1};
  20. 		}
  21. 		int v = que[0];
  22. 		que.pop_front();
  23. 		in_que[v] = 0;
  24. 		for(auto it: g[z][v]) {
  25. 			int u = it.first, c = it.second;
  26. 			if(dist[v] + c < dist[u]) {
  27. 				dist[u] = dist[v] + c;
  28. 				if(!in_que[u]) {
  29. 					in_que[u] = true;
  30. 					que.push_back(u);
  31. 				}
  32. 			}
  33. 		}
  34. 	}
  35. 	return dist;
  36. }
  37.  
  38. void solve() {
  39. 	int N, M;
  40. 	cin >> N >> M;
  41. 	g[0].assign(N, vector<pair<int, int>>());
  42. 	g[1].assign(N, vector<pair<int, int>>());
  43. 	for(int i = 0; i < M; i++) {
  44. 		int t, u, v, c;
  45. 		cin >> t >> u >> v >> c;
  46. 		t--, u--, v--;
  47. 		if(t == 0) {
  48. 			c = -c;
  49. 			swap(u, v);
  50. 		} else {
  51. 			c--;
  52. 		}
  53. 		g[0][v].push_back({u, c});
  54. 		g[1][u].push_back({v, c});
  55. 	}
  56. 	auto le = dist(0, M);
  57. 	auto ge = dist(1, M);
  58. 	for(auto &it: ge) {
  59. 		it = -it;
  60. 	}
  61. 	if(le == ge) {
  62. 		cout << "YES" << endl;
  63. 		for(auto it: le) {
  64. 			cout << it << ' ';
  65. 		}
  66. 		cout << endl;
  67. 	} else {
  68. 		cout << "NO" << endl;
  69. 	}
  70. }
  71.  
  72. signed main() {
  73. 	//freopen("input.txt", "r", stdin);
  74. 	ios::sync_with_stdio(0);
  75. 	cin.tie(0);
  76. 	int t;
  77. 	cin >> t;
  78. 	while(t--) {
  79. 		solve();
  80. 	}
  81. 	return 0;
  82. }
  83.  
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/LGZkqq
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!