当前位置：首页 > news >正文

代码随想录算法训练营第六十四天|卡码网KamaCoder47. 参加科学大会、94. 城市间货物运输 I

news 2026/5/12 11:27:37

47. 参加科学大会

题目链接：47. 参加科学大会
B站讲解

#include<iostream>#include<vector>#include<list>#include<queue>#include<climits>usingnamespacestd;// 小顶堆classmycomparison{public:booloperator()(constpair<int,int>&lhs,constpair<int,int>&rhs){returnlhs.second>rhs.second;}};// 定义一个结构体来表示带权重的边structEdge{intto;// 邻接顶点intval;// 边的权重Edge(intt,intw):to(t),val(w){}// 构造函数};intmain(){intn,m,p1,p2,val;cin>>n>>m;vector<list<Edge>>grid(n+1);for(inti=0;i<m;i++){cin>>p1>>p2>>val;// p1 指向 p2，权值为 valgrid[p1].push_back(Edge(p2,val));}intstart=1;// 起点intend=n;// 终点// 存储从源点到每个节点的最短距离std::vector<int>minDist(n+1,INT_MAX);// 记录顶点是否被访问过std::vector<bool>visited(n+1,false);// 优先队列中存放 pair<节点，源点到该节点的权值>priority_queue<pair<int,int>,vector<pair<int,int>>,mycomparison>pq;// 初始化队列，源点到源点的距离为0，所以初始为0pq.push(pair<int,int>(start,0));minDist[start]=0;// 起始点到自身的距离为0while(!pq.empty()){// 1. 第一步，选源点到哪个节点近且该节点未被访问过 （通过优先级队列来实现）// <节点， 源点到该节点的距离>pair<int,int>cur=pq.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.val<minDist[edge.to]){// 更新minDistminDist[edge.to]=minDist[cur.first]+edge.val;pq.push(pair<int,int>(edge.to,minDist[edge.to]));}}}if(minDist[end]==INT_MAX)cout<<-1<<endl;// 不能到达终点elsecout<<minDist[end]<<endl;// 到达终点最短路径}

94. 城市间货物运输 I

题目链接： 94. 城市间货物运输 I
B站讲解

#include<iostream>#include<vector>#include<list>#include<climits>usingnamespacestd;intmain(){intn,m,p1,p2,val;cin>>n>>m;vector<vector<int>>grid;// 将所有边保存起来for(inti=0;i<m;i++){cin>>p1>>p2>>val;// p1 指向 p2，权值为 valgrid.push_back({p1,p2,val});}intstart=1;// 起点intend=n;// 终点vector<int>minDist(n+1,INT_MAX);minDist[start]=0;for(inti=1;i<n;i++){// 对所有边 松弛 n-1 次for(vector<int>&side:grid){// 每一次松弛，都是对所有边进行松弛intfrom=side[0];// 边的出发点intto=side[1];// 边的到达点intprice=side[2];// 边的权值// 松弛操作// minDist[from] != INT_MAX 防止从未计算过的节点出发if(minDist[from]!=INT_MAX&&minDist[to]>minDist[from]+price){minDist[to]=minDist[from]+price;}}}if(minDist[end]==INT_MAX)cout<<"unconnected"<<endl;// 不能到达终点elsecout<<minDist[end]<<endl;// 到达终点最短路径}