网页设计与网站架设,百度怎么开户做网站,购物网站功能模块,建设团购网站拓扑排序精讲 关键#xff1a; 先找到入度为0的节点#xff0c;把这些节点加入队列/结果#xff0c;然后依次循环再找。 #include iostream
#include vector
#include queue
#include unordered_map
using namespace std;
int main() {int … 拓扑排序精讲 关键 先找到入度为0的节点把这些节点加入队列/结果然后依次循环再找。 #include iostream
#include vector
#include queue
#include unordered_map
using namespace std;
int main() {int m, n, s, t;cin n m;vectorint inDegree(n, 0); // 记录每个文件的入度unordered_mapint, vectorint umap;// 记录文件依赖关系vectorint result; // 记录结果while (m--) {// s-t先有s才能有tcin s t;inDegree[t]; // t的入度加一umap[s].push_back(t); // 记录s指向哪些文件}queueint que;for (int i 0; i n; i) {// 入度为0的文件可以作为开头先加入队列if (inDegree[i] 0) que.push(i);//cout inDegree[i] endl;}// int count 0;while (que.size()) {int cur que.front(); // 当前选中的文件que.pop();//count;result.push_back(cur);vectorint files umap[cur]; //获取该文件指向的文件if (files.size()) { // cur有后续文件for (int i 0; i files.size(); i) {inDegree[files[i]] --; // cur的指向的文件入度-1if(inDegree[files[i]] 0) que.push(files[i]);}}}if (result.size() n) {for (int i 0; i n - 1; i) cout result[i] ;cout result[n - 1];} else cout -1 endl;} dijkstra朴素版精讲 不能处理负权重贪心算法minDist表示距离原点最近的距离。 跟prim一样 #include iostream
#include vector
#include climits
using namespace std;int main(){int n,m,s,e,v;cinnm;vectorvectorint grid(n1,vectorint(n1, INT_MAX));for(int i0;im;i){cinsev;grid[s][e]v;}vectorbool visited(n1, false);vectorint minDist(n1, INT_MAX);int start 1;minDist[start] 0;for(int i0;in;i){int cur -1;int minVal INT_MAX;//1.选择未到过的且距离起始点最近车站for(int j1;jn;j){if(!visited[j] minDist[j]minVal){cur j;minVal minDist[j];}}if(cur -1) {break;}//2.到达该车站visited[cur] true;//3.更新minDistfor(int j1;jn;j){if(!visited[j] grid[cur][j]!INT_MAX minDist[cur]grid[cur][j]minDist[j]){minDist[j] minDist[cur]grid[cur][j];}}// coutcurcurendl;// for(int k1;kn;k){// coutminDist[k] ;// }// coutendl;}int count 0;for(int i1;in;i){if(visited[i]){count;}}if(countn){coutminDist[n]endl;}else{cout-1endl;}}
