给定一个有向图，求1到n的最短路径。需要可以判断图中是否有负环。

区块链毕设网qklbishe.com为您提供问题的解答

给定一个有向图，求1到n的最短路径。
需要可以判断图中是否有负环。

#include<iostream> #include<vector> using namespace std; int inf=1e9; int inline read(){     int x = 0, f = 1;     char c = getchar();     while(c < '0' || c > '9'){         if(c == '-'){             f = -1;         }         c = getchar();     }     while(c >= '0' && c <= '9'){         x = x*10+c-'0';         c = getchar();     }     return x*f; }  int n,m,l,r,w;  vector<int>Map(201);  struct edge{     int from;     int to;     int weight; }; vector<edge>E; bool BF(){     for(int i=0;i<n;i++){         bool flag=false;         for(int j=0;j<m;j++){             if(Map[E[j].to]>Map[E[j].from]+E[j].weight){                 flag=true;                 Map[E[j].to]=Map[E[j].from]+E[j].weight;             }         }         if(!flag)return false;     }     for(int j=0;j<m;j++){         if(Map[E[j].to]>Map[E[j].from]+E[j].weight){             return true;         }     }     return false; }  int main() {     n=read();     m=read();     for(int i=1;i<=n;i++){         Map[i]=inf;     }     Map[1]=0;     for(int i=0;i<m;i++){         l=read();         r=read();         w=read();         E.push_back({l,r,w});     }     if(BF()){         printf("circlen");         return 0;     }     if(Map[n]==inf){         printf("can't arrive!n");         return 0;     }     printf("%dn",Map[n]);     return 0; }

23:51

以上就是关于问题给定一个有向图，求1到n的最短路径。
需要可以判断图中是否有负环。的答案

欢迎关注区块链毕设网-
专业区块链毕业设计成品源码，定制。

区块链NFT链游项目方科学家脚本开发培训