单源最短路总结
文章目服务器托管网录
- 单源最短路总结
-
- 建图方式
-
- 普通无向图+邻接表建图
- 新建源点建图
- 正反建图+spfa
- 单源最短路综合运用
-
- dijkstra+dfs
- dijkstra+二分答案
- 未完待续…….
建图方式
-
普通无向图+邻接表建图
板子题
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题库
单源最短路综合运用
dijkstra+dfs
很板,没什么特点。
1135. 新年好 – AcWing题库
#include
using namespace std;
#define ll long long
#define int long long
#define INF 1e10
#define PII pairint,int>
struct ggg{
int v;
int w;
};
ll ans=0;
vectorint> dijkstra(vectorggg>*gg,int n,int start){
vectorint> dist(n+1,INF);
vectorbool> flag(n+1);
priority_queuePII,vectorPII>,greaterPII>> q;
dist[start]=0;
q.push({dist[start],start});
while(q.size()){
int u=q.top().second;
q.pop();
if(flag[u])continue;
for(auto i:gg[u]){
int v=i.v;
int w=i.w;
if(dist[v]>dist[u]+w){
dist[v]=dist[u]+w;
q.push({dist[v],v});
}
}
}
return dist;
}
signed main(){
int n,m;
cin>>n>>m;
vectorint> t(5);
for(int i=0;i5;i++)cin>>t[i];
vectorggg> gg[n+1];
while(m--){
int u,v,w;
cin>>u>>v>>w;
gg[u].push_back(ggg{v,w});
gg[v].push_back(ggg{u,w});
}
vectorint> a(5);
vectorint> dist[n+1];
dist[1]=dijkstra(gg,n,1);
for(int i=0;i5;i++){
a[i]=i;
dist[t[i]]=dijkstra(gg,n,t[i]);
}
int ans=0;
int bns=1e10;
ans=0;
ans+=dist[1][t[0]];
for(int i=0;i4;i++){
ans+=dist[t[i]][t[i+1]];
}
bns=min(bns,ans);
while(next_permutation(a.begin(),a.end())){
ans=0;
ans+=dist[1][t[a[0]]];
for(int i=0;i4;i++){
ans+=dist[t[a[i]]][t[a[i+1]]];
}
bns=min(bns,ans);
}
coutbnsendl;
}
dijkstra+二分答案
二分可行性
340. 通信线路 – AcWing题库
#include
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(n+1,INF);
vectorbool> flag(n+1);
priority_queuePII,vectorPII>,greaterPII> > q;
dist[1]=0;
q.push({0,1});
while(q.size()){
int u=q.top().second;
q.pop();
if(flag[u])continue;
flag[u]=1;
for(auto i:gg[u]){
int v=i.v;
int w=i.w;
if(dist[v]>di服务器托管网st[u]+(w>=k?1:0)){
dist[v]=dist[u]+(w>=k?1:0);
q.push({dist[v],v});
}
}
}
return dist[n]K;
}
signed main(){
int n,p,k;
cin>>n>>p>>k;
vectorggg> gg[n+1];
while(p--){
int u,v,w;
cin>>u>>v>>w;
gg[u].push_back({v,w});
gg[v].push_back({u,w});
}
int l=0; int r=1e9,mid;
while(lr){
mid=l+r+1>>1;
if(spfa(gg,n,mid,k)){
r=mid-1;
}
else l=mid;
}
if(r!=1e9)
coutrendl;
else cout-1endl;
}
未完待续…
服务器托管,北京服务器托管,服务器租用 http://www.fwqtg.net
相关推荐: TensorFlow2实战-系列教程6:迁移学习实战
TensorFlow2实战-系列教程 总目录 有任何问题欢迎在下面留言 本篇文章的代码运行界面均在Jupyter Notebook中进行 本篇文章配套的代码资源已经上传 1、迁移学习 用已经训练好模型的权重参数当做自己任务的模型权重初始化 一般全连接层需要自己…