Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _USE_MATH_DEFINES
- #include<stdio.h>
- #include<iostream>
- #include<vector>
- #include<cmath>
- #include<algorithm>
- #include<memory.h>
- #include<map>
- #include<set>
- #include<queue>
- #include<list>
- #include<sstream>
- #include<cstring>
- #include<numeric>
- #include<limits.h>
- #include<stack>
- using namespace std;
- const int N = 1e2 + 1;
- const int S = 1e6 + 1;
- const int delta = 1e5;
- const int INF = 1e9;
- int s;
- vector<int> g[N];
- set<int> gs[N];
- bool mu = false;
- bool k = false;
- void addEdge(int a, int b) {
- g[a].push_back(b);
- g[b].push_back(a);
- if (a == b) {
- k = true;
- }
- if (gs[a].count(b) != 0) {
- mu = true;
- }
- if (gs[b].count(a) != 0) {
- mu = true;
- }
- gs[a].insert(b);
- gs[b].insert(a);
- }
- bool u[N];
- bool c = false;
- int p[N];
- void dfsCycle(int v) {
- u[v] = true;
- for (auto to : g[v]) {
- if (u[to]) {
- if (p[v] != to) {
- c = true;
- return;
- }
- }
- else {
- p[to] = v;
- dfsCycle(to);
- }
- }
- }
- int d[N][N];
- int n, m;
- int main() {
- #ifndef ONLINE_JUDGE
- freopen("input.txt", "r", stdin);
- #endif
- scanf("%d%d%d", &n, &m, &s);
- for (int i = 0; i < m; i++) {
- int a, b, c;
- scanf("%d%d%d", &a, &b, &c);
- addEdge(a - 1, b - 1);
- d[a - 1][b - 1] = -c;
- d[b - 1][a - 1] = -c;
- }
- for (int i = 0; i < n; ++i) {
- if (!u[i]) {
- dfsCycle(i);
- if (c)
- break;
- }
- }
- if (c || mu || k) {
- printf("YES");
- return 0;
- }
- for (int i = 0; i < n; i++) {
- for (int j = 0; j < n; j++) {
- if (i == j) d[i][j] = 0;
- else if (d[i][j] == 0) d[i][j] = INF;
- }
- }
- int res = 0;
- for (int k = 0; k < n; ++k) {
- for (int i = 0; i < n; ++i) {
- for (int j = 0; j < n; ++j) {
- if (d[i][k] < INF && d[k][j] < INF) {
- d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
- }
- }
- }
- }
- for (int i = 0; i < n; i++) {
- for (int j = 0; j < n; j++) {
- if (d[i][j] != -INF) {
- res = max(res, -d[i][j]);
- }
- }
- }
- printf(res >= s ? "YES" : "NO");
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement