uva558
时间:2022-04-30 20:38
题目链接请戳
解题思路
用bellman-ford算法判断,邻接表实现。
代码
#include#include using namespace std; const int N = 1010; const int INF = 1e9; struct edge { int u, v, time; edge(int uu, int vv, int cc):u(uu),v(vv),time(cc) {} edge() {} }; vector edges; int dist[N]; int n, m; bool Bellman(int k) { for (int i = 0; i < n; i++) dist[i] = INF; dist[k] = 0; //最短路最多n-1条边 for (int i = 0; i < n - 1; i++) { for (int j = 0; j < m; j++) { int u = edges[j].u; int v = edges[j].v; if (dist[v] > dist[u] + edges[j].time) dist[v] = dist[u] + edges[j].time; } } //试着松弛,如果可以继续松弛,则有负环 for (int j = 0; j < m; j++) { int u = edges[j].u; int v = edges[j].v; if (dist[v] > dist[u] + edges[j].time) return true; } return false; } int main() { int tests; cin >> tests; while (tests--) { cin >> n >> m; edges.clear(); for (int i = 0; i < m; i++) { int u, v, time; cin >> u >> v >> time; edge temp(u, v, time); edges.push_back(temp); } if (Bellman(0)) cout << "possible" << endl; else cout << "not possible" << endl; } return 0; }