#include<iostream> #include<vector> #include<algorithm> #include<string> #include<climits> #include<cmath> #include<map> #include<set> using namespace std; vector<vector<int>> city(1001, vector<int>(1001, 0)); //bool dfs(int time, int pos, int n) { // // if (pos == 1 && time < 0) // return true; // if (pos == 1 && time >= 0) // return false; // // for (int i = n - 1; i >= 1; i--) { // // if (city[i][pos] != 0) { //存在路径 // // if (dfs(time + city[i][pos], i, n)) // return true; // } // } // // return false; //} int main() { int m, n; while (cin >> n >> m) { vector<vector<int>> dp(n + 1, vector<int>(n + 1, INT_MAX)); for (int i = 0; i < m; i++) { int a, b, t; cin >> a >> b >> t; city[a][b] = t; } for (int i = 1; i <= n; i++) { for (int j = 2; j <= n; j++) { if (city[i][j] != 0) { if (i != 1) { dp[1][j] = min(dp[1][j], dp[1][i] + city[i][j]); } else dp[1][j] = city[1][j]; } } } if(dp[1][n] < 0) cout << "YES" << endl; else cout << "NO" << endl; //if (dfs(0, n, n)) // cout << "YES" << endl; //else // cout << "NO" << endl; } } |
Double click to view unformatted code.