要建设一个网站,微信开发者工具,欧米茄表官方官网,互联网网站备案流程单源最短路总结 文章目录 单源最短路总结建图方式普通无向图邻接表建图新建源点建图正反建图spfa 单源最短路综合运用dijkstradfsdijkstra二分答案 未完待续....... 建图方式 普通无向图邻接表建图
板子题
1129. 热浪 - AcWing题库
找最短路里的最长路
1128. 信使 - AcWin…单源最短路总结 文章目录 单源最短路总结建图方式普通无向图邻接表建图新建源点建图正反建图spfa 单源最短路综合运用dijkstradfsdijkstra二分答案 未完待续....... 建图方式 普通无向图邻接表建图
板子题
1129. 热浪 - AcWing题库
找最短路里的最长路
1128. 信使 - AcWing题库
经典问题在无向图中找一点使得其他点到该点距离最小
跑n遍最短路即可
1127. 香甜的黄油 - AcWing题库
考察对dijkstra贪心本质的理解修改了最短路更新的形式
也可以不想这些用数学构造出一个新的最短路
1126. 最小花费 - AcWing题库
集合之间的最短路问题有n个连通块求到终点最少经过几个连通块。
处理方式很简单只要让每一条边的边权都为1跑一遍最短路即可原理也很简单可以自行推导
920. 最优乘车 - AcWing题库 新建源点建图
有一些题看不出来是最短路是因为他没有直接问你从起点到终点的最短路。
例如超市购物问题/以物易物问题
903. 昂贵的聘礼 - AcWing题库
这时候就可以通过建立一个新的源点0然后用0作为起点建图 正反建图spfa
刷到一道题需要我们找到1~N这条路径里的两个有序的点一个在前一个在后。
然后让后减前得到最大值。
由于这两个点是在1~N这条路径上所以最好用spfa
另外我们让前面最小让后面最大怎么办
首先我们就要界定一个中间点i
然后求出 1~i 的小权值和i~n的最大权值即可
前者我们以1为起点跑一遍spfa即可
后者我们不可能以i为点跑spfa这样复杂度过高。
所以需要以n为起点这样只要一遍就可以得到答案
但是由于可能会有单向边
所以最好反过来建图
341. 最优贸易 - AcWing题库
单源最短路综合运用
dijkstradfs
很板没什么特点。
1135. 新年好 - AcWing题库
#includebits/stdc.h
using namespace std;
#define ll long long
#define int long long
#define INF 1e10
#define PII pairint,intstruct ggg{int v;int w;
};ll ans0;vectorint dijkstra(vectorggg*gg,int n,int start){vectorint dist(n1,INF);vectorbool flag(n1);priority_queuePII,vectorPII,greaterPII q;dist[start]0;q.push({dist[start],start});while(q.size()){int uq.top().second;q.pop();if(flag[u])continue;for(auto i:gg[u]){int vi.v;int wi.w;if(dist[v]dist[u]w){dist[v]dist[u]w;q.push({dist[v],v});}}}return dist;}
signed main(){int n,m;cinnm;vectorint t(5);for(int i0;i5;i)cint[i];vectorggg gg[n1];while(m--){int u,v,w;cinuvw;gg[u].push_back(ggg{v,w});gg[v].push_back(ggg{u,w});}vectorint a(5);vectorint dist[n1];dist[1]dijkstra(gg,n,1);for(int i0;i5;i){a[i]i;dist[t[i]]dijkstra(gg,n,t[i]);}int ans0;int bns1e10;ans0;ansdist[1][t[0]];for(int i0;i4;i){ansdist[t[i]][t[i1]];}bnsmin(bns,ans);while(next_permutation(a.begin(),a.end())){ans0;ansdist[1][t[a[0]]];for(int i0;i4;i){ansdist[t[a[i]]][t[a[i1]]];}bnsmin(bns,ans);}coutbnsendl;
}dijkstra二分答案
二分可行性
340. 通信线路 - AcWing题库
#includebits/stdc.h
using namespace std;
#define ll long long
#define INF 1e9
#define PII pairll,ll
//#define int long long
struct ggg{int v;int w;
};int spfa(vectorggg*gg,int n,int k,int K){vectorll dist(n1,INF);vectorbool flag(n1);priority_queuePII,vectorPII,greaterPII q;dist[1]0;q.push({0,1});while(q.size()){int uq.top().second;q.pop();if(flag[u])continue;flag[u]1;for(auto i:gg[u]){int vi.v;int wi.w;if(dist[v]dist[u](wk?1:0)){dist[v]dist[u](wk?1:0);q.push({dist[v],v});}}}return dist[n]K;
}signed main(){int n,p,k;cinnpk;vectorggg gg[n1];while(p--){int u,v,w;cinuvw;gg[u].push_back({v,w});gg[v].push_back({u,w});}int l0; int r1e9,mid;while(lr){midlr11;if(spfa(gg,n,mid,k)){rmid-1;}else lmid;}if(r!1e9)coutrendl;else cout-1endl;}未完待续…
