邯郸做网站就找安联网络,建网站中企动力最行,新媒体营销h5制作网站,网站优化查询代码目录 117. 软件构建
拓扑排序法
47. 参加科学大会
dijkstra法 117. 软件构建 题目链接#xff1a;117. 软件构建 文章讲解#xff1a;代码随想录
拓扑排序法 代码一#xff1a;拓扑排序
#include iostream
#include vector
#include queue
…目录 117. 软件构建
拓扑排序法
47. 参加科学大会
dijkstra法 117. 软件构建 题目链接117. 软件构建 文章讲解代码随想录
拓扑排序法 代码一拓扑排序
#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;}47. 参加科学大会 题目链接47. 参加科学大会(第六期模拟笔试) 文章讲解代码随想录
dijkstra法 代码一dijkstra
#include iostream
#include vector
#include climits
using namespace std;
int main() {int n, m, p1, p2, val;cin n m;vectorvectorint grid(n 1, vectorint(n 1, INT_MAX));for(int i 0; i m; i){cin p1 p2 val;grid[p1][p2] val;}int start 1;int end n;// 存储从源点到每个节点的最短距离std::vectorint minDist(n 1, INT_MAX);// 记录顶点是否被访问过std::vectorbool visited(n 1, false);minDist[start] 0; // 起始点到自身的距离为0for (int i 1; i n; i) { // 遍历所有节点int minVal INT_MAX;int cur 1;// 1、选距离源点最近且未访问过的节点for (int v 1; v n; v) {if (!visited[v] minDist[v] minVal) {minVal minDist[v];cur v;}}visited[cur] true; // 2、标记该节点已被访问// 3、第三步更新非访问节点到源点的距离即更新minDist数组for (int v 1; v n; v) {if (!visited[v] grid[cur][v] ! INT_MAX minDist[cur] grid[cur][v] minDist[v]) {minDist[v] minDist[cur] grid[cur][v];}}}if (minDist[end] INT_MAX) cout -1 endl; // 不能到达终点else cout minDist[end] endl; // 到达终点最短路径}
