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;
- int s;
- vector<pair<int, int>> g[N];
- set<int> gs[N];
- bool mu = false;
- bool k = false;
- void addEdge(int a, int b, int c) {
- g[a].push_back(make_pair(b, c));
- g[b].push_back(make_pair(a, c));
- 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.first]) {
- if (p[v] != to.first) {
- c = true;
- return;
- }
- }
- else {
- p[to.first] = v;
- dfsCycle(to.first);
- }
- }
- }
- int n, m;
- int dijkstra(int s) {
- vector<int> d(n, LONG_MAX), p(n, -1);
- vector<int> r(n, 0);
- d[s] = 0;
- r[0] = 0;
- set < pair<int, int> > q;
- q.insert(make_pair(d[s], s));
- while (!q.empty()) {
- int v = q.begin()->second;
- q.erase(q.begin());
- for (size_t j = 0; j<g[v].size(); ++j) {
- int to = g[v][j].first,
- len = g[v][j].second;
- if (d[v] + len < d[to]) {
- q.erase(make_pair(d[to], to));
- d[to] = d[v] + len;
- r[to] = r[v] + 1;
- p[to] = v;
- q.insert(make_pair(d[to], to));
- }
- }
- }
- int res = 0;
- for (int i = 0; i < n; i++) {
- if (d[i] != LONG_MAX) {
- int cur = -(d[i] - delta * r[i]);
- res = max(res, cur);
- }
- }
- return res;
- }
- 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, -c + delta);
- }
- for (int i = 0; i < n; ++i) {
- if (!u[i]) {
- dfsCycle(i);
- if (c)
- break;
- }
- }
- if (c || mu || k) {
- printf("YES");
- return 0;
- }
- int res = 0;
- for (int i = 0; i < n; i++) {
- res = max(res, dijkstra(i));
- }
- printf(res >= s ? "YES" : "NO");
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement