47. 参加科学大会题目链接47. 参加科学大会B站讲解#includeiostream#includevector#includelist#includequeue#includeclimitsusingnamespacestd;// 小顶堆classmycomparison{public:booloperator()(constpairint,intlhs,constpairint,intrhs){returnlhs.secondrhs.second;}};// 定义一个结构体来表示带权重的边structEdge{intto;// 邻接顶点intval;// 边的权重Edge(intt,intw):to(t),val(w){}// 构造函数};intmain(){intn,m,p1,p2,val;cinnm;vectorlistEdgegrid(n1);for(inti0;im;i){cinp1p2val;// p1 指向 p2权值为 valgrid[p1].push_back(Edge(p2,val));}intstart1;// 起点intendn;// 终点// 存储从源点到每个节点的最短距离std::vectorintminDist(n1,INT_MAX);// 记录顶点是否被访问过std::vectorboolvisited(n1,false);// 优先队列中存放 pair节点源点到该节点的权值priority_queuepairint,int,vectorpairint,int,mycomparisonpq;// 初始化队列源点到源点的距离为0所以初始为0pq.push(pairint,int(start,0));minDist[start]0;// 起始点到自身的距离为0while(!pq.empty()){// 1. 第一步选源点到哪个节点近且该节点未被访问过 通过优先级队列来实现// 节点 源点到该节点的距离pairint,intcurpq.top();pq.pop();if(visited[cur.first])continue;// 2. 第二步该最近节点被标记访问过visited[cur.first]true;// 3. 第三步更新非访问节点到源点的距离即更新minDist数组for(Edge edge:grid[cur.first]){// 遍历 cur指向的节点cur指向的节点为 edge// cur指向的节点edge.to这条边的权值为 edge.valif(!visited[edge.to]minDist[cur.first]edge.valminDist[edge.to]){// 更新minDistminDist[edge.to]minDist[cur.first]edge.val;pq.push(pairint,int(edge.to,minDist[edge.to]));}}}if(minDist[end]INT_MAX)cout-1endl;// 不能到达终点elsecoutminDist[end]endl;// 到达终点最短路径}94. 城市间货物运输 I题目链接 94. 城市间货物运输 IB站讲解#includeiostream#includevector#includelist#includeclimitsusingnamespacestd;intmain(){intn,m,p1,p2,val;cinnm;vectorvectorintgrid;// 将所有边保存起来for(inti0;im;i){cinp1p2val;// p1 指向 p2权值为 valgrid.push_back({p1,p2,val});}intstart1;// 起点intendn;// 终点vectorintminDist(n1,INT_MAX);minDist[start]0;for(inti1;in;i){// 对所有边 松弛 n-1 次for(vectorintside:grid){// 每一次松弛都是对所有边进行松弛intfromside[0];// 边的出发点inttoside[1];// 边的到达点intpriceside[2];// 边的权值// 松弛操作// minDist[from] ! INT_MAX 防止从未计算过的节点出发if(minDist[from]!INT_MAXminDist[to]minDist[from]price){minDist[to]minDist[from]price;}}}if(minDist[end]INT_MAX)coutunconnectedendl;// 不能到达终点elsecoutminDist[end]endl;// 到达终点最短路径}