1思路:利用Bellman_Ford来判断是否存在回环
2分析:在利用Bellman_Fordde 时候如果做了n-1次的松弛步以后还能更新dis数组,那么说明原来的图中存在环,那么最短路就是不存在的。
代码:
#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> using namespace std; #define MAXN 2010 #define INF 0xFFFFFFF int t , n , m; int dis[MAXN]; struct Edge{ int x; int y; int value; }e[MAXN]; bool judge(){ for(int i = 0 ; i < m ; i++){ if(dis[e[i].y] > dis[e[i].x] + e[i].value) return false; } return true; } void Bellman_Ford(){ dis[0] = 0; for(int i = 1 ; i < n ; i++) dis[i] = INF; for(int i = 0 ; i < n ; i++){ for(int j = 0 ; j < m ; j++){ if(dis[e[j].y] > dis[e[j].x] + e[j].value) dis[e[j].y] = dis[e[j].x] + e[j].value; } } if(judge()) printf("not possible\n"); else printf("possible\n"); } int main(){ scanf("%d", &t); while(t--){ scanf("%d%d" , &n , &m); for(int i = 0 ; i < m ; i++) scanf("%d%d%d" , &e[i].x , &e[i].y , &e[i].value); Bellman_Ford(); } return 0; }
时间: 2024-07-31 10:02:01