虾皮跨境电商网站,虚拟主机怎么弄网站,北京爱空间装修公司,宣城网站建设刷题记录 94. 城市间货物运输 I-Bellman_ford 队列优化算法#xff08;SPFA#xff09;95. 城市间货物运输 II-BF算法判断负回路96. 城市间货物运输 III-BF之单源有限最短路(有负回路) 94. 城市间货物运输 I-Bellman_ford 队列优化算法#xff08;SPFA#xff09;
题目地址… 刷题记录 94. 城市间货物运输 I-Bellman_ford 队列优化算法SPFA95. 城市间货物运输 II-BF算法判断负回路96. 城市间货物运输 III-BF之单源有限最短路(有负回路) 94. 城市间货物运输 I-Bellman_ford 队列优化算法SPFA
题目地址
SPFA讲解
时间复杂度 O ( n ) O(n) O(n) 空间复杂度 O ( n ) O(n) O(n)
// c
#includebits/stdc.h
using namespace std;
struct Edge{int to;int val;Edge(int t, int v): to(t), val(v){}
};
int main(){int n,m,left,right,val;cinnm;vectorlistEdge edges(n1);for(int i0; im; i){cinleftrightval;edges[left].push_back(Edge(right, val));}int start 1;int end n;vectorint minDist(n1, INT_MAX);vectorbool isInQue(n1, false);minDist[start] 0;queueint que;que.push(start);while(!que.empty()){int cur que.front();que.pop();isInQue[cur] false;for(Edge edge:edges[cur]){int to edge.to;int val edge.val;if(minDist[cur]valminDist[to]){minDist[to] minDist[cur]val;if(!isInQue[to]){que.push(to);isInQue[to] true;}}}}/*// 对所有边松弛n-1次for(int i0; in; i){for(vectorint edge : edges){int from edge[0];int to edge[1];int val edge[2];// 松弛操作if(minDist[from] ! INT_MAX minDist[to] minDist[from]val){minDist[to] minDist[from]val;}}}*/if(minDist[end] INT_MAX) coutunconnected;else coutminDist[end];return 0;
}95. 城市间货物运输 II-BF算法判断负回路
题目地址
BF算法对图中的边至多松弛n-1次即可得到单源最短路径。若n-1次松弛后再遍历仍有更新操作则判定为图中出现负回路。
时间复杂度 O ( V ∗ E ) O(V * E) O(V∗E) 空间复杂度 O ( V ) O(V) O(V)
// c
#includebits/stdc.h
using namespace std;int main(){int n,m;cinnm;vectorvectorint edges;vectorint minDist(n1, INT_MAX);int left, right, val;for(int i0; im; i){cinleftrightval;edges.push_back({left, right, val});}minDist[1] 0;for(int i1; in; i){for(vectorint edge : edges){int from edge[0];int to edge[1];int val edge[2];if(minDist[from]!INT_MAX minDist[from]valminDist[to]){minDist[to] minDist[from] val;}}}bool flagfalse;for(vectorint edge : edges){int from edge[0];int to edge[1];int val edge[2];if(minDist[from]!INT_MAX minDist[from]valminDist[to]){minDist[to] minDist[from] val;flag true;}}if(flag) {std::cout circle std::endl;}else{if(minDist[n]!INT_MAX){coutminDist[n]endl;}else{coutunconnected;}}return 0;
}96. 城市间货物运输 III-BF之单源有限最短路(有负回路)
题目地址
BF算法对所有边松弛n-1次可以得到源点到与源点n-1条边n个结点相连的结点的最短距离。本题要求最多经过k个城市的最短路径也就是除去起点和终点中间有k个结点共k1个结点因此有k1条边BF算法松弛k1次。
在有负权值回路的图中若使用本次松弛结点的最短距离来更新其他结点会导致陷入在负权值回路中因此要基于上一次松弛的结果来更新本次结点。
讲解
时间复杂度 O ( V ∗ E ) O(V * E) O(V∗E) 空间复杂度 O ( V ) O(V) O(V)
// c
#includebits/stdc.h
using namespace std;
int main(){int n,m,from,to,val,src,dst,k;cinnm;vectorvectorint edges;for(int i0; im; i){cinfromtoval;edges.push_back({from, to, val});}cinsrcdstk;vectorint minDist(n1, INT_MAX);vectorint minDist_copy(n1);minDist[src] 0;for(int i0; ik; i){minDist_copy minDist;for(vectorint edge : edges){from edge[0];to edge[1];val edge[2];if(minDist_copy[from]!INT_MAX minDist_copy[from]valminDist[to]){minDist[to] minDist_copy[from]val;}}// for (int j 1; j n; j) cout minDist[j] ;// cout endl;}if(minDist[dst] ! INT_MAX) {coutminDist[dst];}else{coutunreachable;}return 0;
}
