洛谷题单 Part 8.2 最短路问题

这篇具有很好参考价值的文章主要介绍了洛谷题单 Part 8.2 最短路问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

0. 0. 0.写在前面

最短路算法一般在算法竞赛中有四种比较常见, F l o y d Floyd Floyd算法, B e l l m a n − F o r d Bellman-Ford BellmanFord算法, D i j k s t r a Dijkstra Dijkstra算法, S P F A SPFA SPFA算法。
F l o y d Floyd Floyd算法和 B e l l m a n − F o r d Bellman-Ford BellmanFord算法的时间复杂度分别为 O ( n 3 ) O(n^3) O(n3) O ( n m ) O(nm) O(nm)
D i j k s t r a Dijkstra Dijkstra算法的时间复杂度为 O ( n 2 ) O(n^2) O(n2),用堆优化之后的复杂度可以稳定在 O ( n log ⁡ n ) O(n\log n) O(nlogn),是目前使用最多的最短路算法,在各大网络地图中都有应用。缺点是不能求单点对单点的最短路,只能将单点到所有点的最短路求出,而且仅适用于有向加权图,无法处理边为负值的图。
S P F A SPFA SPFA算法的本质是 B e l l m a n − F o r d Bellman-Ford BellmanFord算法的改良版本,但其实更像一种贪心算法,时间复杂度为 O ( k m ) O(km) O(km),但会被卡到 O ( n m ) O(nm) O(nm),有几种优化可以解决部分情况,具体看我早年的一篇博客SPFA的几种优化以及Hack的方法,不过就是再好的优化也会被卡,所以大部分题建议无脑 d i j k + dijk+ dijk+堆优化。

1. 1. 1.例题

P3371 【模板】单源最短路径(弱化版)

题面
S o l u t i o n : Solution: Solution: d i j k s t r a dijkstra dijkstra算法求出单点到所有点的最短路即可,由于 n < = 1 e 4 n<=1e4 n<=1e4,不需要堆优化。

#include<bits/stdc++.h>
#define N 10010
#define M 500050
#define reg register
using namespace std;
inline void read(int &x){
    int s=0,w=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){s=(s<<3)+(s<<1)+(ch&15);ch=getchar();}
    x=s*w;
}
struct node{
    int to,nxt,val;
}edge[M<<1];
int n,m,s,u,v,w,cnt,head[N],dis[N],vis[N];
inline void addedge(int u, int v, int w){
    edge[++cnt].to=v,edge[cnt].nxt=head[u],edge[cnt].val=w,head[u]=cnt;
}
inline void superadd(int u, int v, int w){
    addedge(u,v,w),addedge(v,u,w);
}
void dijkstra(){
    memset(dis,0x3f3f3f3f,sizeof dis);
    dis[s]=0;
    int x=s;
    while(x){
        x=0;
        for(int i=1;i<=n;i++)if(dis[i]<dis[x]&&!vis[i])x=i;
        vis[x]=1;
        for(int i=head[x];i;i=edge[i].nxt){
            int v=edge[i].to;
            dis[v]=min(dis[v],dis[x]+edge[i].val);
        }
    }
}
int main(){
    read(n),read(m),read(s);
    for(reg int i=1;i<=m;i++)read(u),read(v),read(w),addedge(u,v,w);
    dijkstra();
    for(reg int i=1;i<=n;i++){
        if(dis[i]==dis[0])printf("2147483647 ");
        else printf("%d ",dis[i]);
    }
    putchar('\n');
}


P4779 【模板】单源最短路径(标准版)

题面
S o l u t i o n : Solution: Solution:由于边的数量超过了 1 e 5 1e5 1e5,所以 O ( n 2 ) O(n^2) O(n2)的算法是过不了,我们选择堆优化的 d i j k s t r a dijkstra dijkstra算法进行求解。

#include<bits/stdc++.h>
#define N 100100
#define M 500050
#define reg register
using namespace std;
inline void read(int &x){
    int s=0,w=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){s=(s<<3)+(s<<1)+(ch&15);ch=getchar();}
    x=s*w;
}
struct node{
    int to,nxt,val;
}edge[M<<1];
struct pnt{
    int d,p;
    bool operator <(const pnt &x) const{
        return x.d<d;
    }
};
priority_queue<pnt> q;
int n,m,s,u,v,w,cnt,head[N],dis[N],vis[N];
inline void addedge(int u, int v, int w){
    edge[++cnt].to=v,edge[cnt].nxt=head[u],edge[cnt].val=w,head[u]=cnt;
}
inline void superadd(int u, int v, int w){
    addedge(u,v,w),addedge(v,u,w);
}
void dijkstra(){
    memset(dis,0x3f3f3f3f,sizeof dis);
    dis[s]=0;
    pnt x;x.d=0,x.p=s;q.push(x);
    while(!q.empty()){
        x=q.top();q.pop();
        if(vis[x.p])continue;
        vis[x.p]=1;
        for(int i=head[x.p];i;i=edge[i].nxt){
            int v=edge[i].to;
            dis[v]=min(dis[v],dis[x.p]+edge[i].val);
            if(!vis[v]){
                pnt y;y.d=dis[v],y.p=v;
                q.push(y);
            }
        }
    }
}
int main(){
    read(n),read(m),read(s);
    for(reg int i=1;i<=m;i++)read(u),read(v),read(w),addedge(u,v,w);
    dijkstra();
    for(reg int i=1;i<=n;i++){
        if(dis[i]==dis[0])printf("2147483647 ");
        else printf("%d ",dis[i]);
    }
    putchar('\n');
}
P5905 【模板】Johnson 全源最短路

题面
S o l u t i o n : Solution: Solution:本题要求每个点到所有点的最短路径,并且带有负边权,如果在没有负边权的情况下可以用 n n n次堆优化的 d i j k s t r a dijkstra dijkstra算法在 O ( n 2 l o g n ) O(n^2log_n) O(n2logn)的时间计算出答案,但是这题有负边权,所以现在应考虑如何处理负边权。
首先考虑将所有加上一个较大的值,那么将不保证正确性,比如从 a a a b b b,一条路是 a − > c 1 − > b a->c_1->b a>c1>b,一条路是 a − > c 1 − > c 2 − > b a->c_1->c_2->b a>c1>c2>b,假设边权都为 − 1 -1 1,显然第二条路是最短路,但将每个边都加上一个较大的值后第一条路就变为最短路了。
这里介绍 J o h n s o n Johnson Johnson算法处理负边权,我们新建一个 0 0 0结点,并将其向所有点连一条边权为 0 0 0的一条边,接着用 B e l l m a n − F o r d Bellman-Ford BellmanFord算法求解 0 0 0到所有边的最短路,记为 d i d_i di,假如存在一条从 u u u v v v边权为 w w w的边,我们将其边权修改为 w + d u − d v w+d_u-d_v w+dudv,这样所有边权就被修改为非负的,且不会影响正确性。
如何理解 J o h n s o n Johnson Johnson算法呢,我们可以将 d i d_i di理解为以 0 0 0结点为零势能点的势能大小,无论从 u u u v v v走什么样的路径, d u − d v d_u-d_v dudv是一个定值。其次如何证明修改操作过后的所有边为非负的呢,由于 d u , d v d_u,d_v du,dv是从 0 0 0结点到 u , v u,v u,v结点的最短路,故从 0 0 0 u u u再到 v v v的路径一定大于等于 d v d_v dv,即 d v ≤ d u + w d_v\leq d_u+w dvdu+w因此 w + d u − d v ≥ 0 w+d_u-d_v\geq0 w+dudv0,故所有边权为非负,此时再用 n n n d i j k s t r a dijkstra dijkstra算法进行求解即可。
注意本题可能有负环,应先用 s p f a spfa spfa判一遍负环,再进行求解,可以直接用 s p f a spfa spfa更新 d d d数组,顺便进行判负环操作。

#include<bits/stdc++.h>
#define N 3030
#define M 6060
#define reg register 
using namespace std;
inline void read(int &x){
    int s=0,w=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){s=(s<<3)+(s<<1)+(ch&15);ch=getchar();}
    x=s*w;
}
struct node{
    int to,val,nxt;
}edge[M<<1];
struct pnt{
    int dis,pos;
    bool operator <(const pnt &x) const{
        return x.dis<dis;
    }
};
int n,m,s,u,v,w,cnt,head[N],tot[N],vis[N],dis[N],f[N];
inline void addedge(int u, int v, int w){
    edge[++cnt].to=v,edge[cnt].nxt=head[u],head[u]=cnt,edge[cnt].val=w;
}
inline void superadd(int u, int v, int w){
    addedge(u,v,w),addedge(v,u,w);
}
bool spfa(int s){
    queue<int> q;
    memset(vis,0,sizeof vis);
    memset(f,0x3f,sizeof f);
    f[s]=0,vis[s]=1;
    q.push(s);
    while(!q.empty()){
        int u=q.front();
        q.pop();vis[u]=false;
        for(int i=head[u];i;i=edge[i].nxt){
            int v=edge[i].to;
            if(f[v]>f[u]+edge[i].val){
                f[v]=f[u]+edge[i].val;
                if(!vis[v]){
                    vis[v]=true,tot[v]++;q.push(v);
                    if(tot[v]>n)return false;
                }
            }
        }
    }
    return true;
}
void dijkstra(int s){
    memset(dis,0x7f,sizeof dis);
    memset(vis,0,sizeof vis);
    priority_queue<pnt> q;
    dis[s]=0;
    pnt x;x.dis=0,x.pos=s;q.push(x);
    while(!q.empty()){
        x=q.top();q.pop();
        if(vis[x.pos])continue;
        vis[x.pos]=true;
        for(reg int i=head[x.pos];i;i=edge[i].nxt){
            int v=edge[i].to;
            if(dis[v]>dis[x.pos]+edge[i].val){
                dis[v]=dis[x.pos]+edge[i].val;
                if(!vis[v]){
                    pnt y;y.dis=dis[v],y.pos=v;
                    q.push(y);
                }
            }
        }
    }
    return ;
}
int main(){
    read(n),read(m);
    for(reg int i=1;i<=m;i++)read(u),read(v),read(w),addedge(u,v,w);
    for(reg int i=1;i<=n;i++)addedge(0,i,0);
    if(!spfa(0)){
        puts("-1");return 0;
    }
    for(int u=1;u<=n;u++){
        for(int j=head[u];j;j=edge[j].nxt){
            int v=edge[j].to;
            edge[j].val+=f[u]-f[v];
        }
    }
    for(int i=1;i<=n;i++){
        dijkstra(i);
        long long ans=0;
        for(int j=1;j<=n;j++){
            if(dis[j]==dis[n+1])ans+=j*(long long)(1e9);
            else ans+=j*(long long)(dis[j]+f[j]-f[i]);
        }
        cout<<ans<<endl;
    }
}
P1144 最短路计数

题面
S o l u t i o n : Solution: Solution:本题要求无向无权图中单点到所有点最短路的数目,我们将无权图每条边的边权默认为1,则起点到某一点的最短路即为从起点开始 b f s bfs bfs,遍历到该点的深度。我们考虑求最短路的过程,即更新 d i s dis dis数组的过程,当 d i s [ v ] > d i s [ u ] + v a l u e dis[v]>dis[u]+value dis[v]>dis[u]+value时,取 d i s [ v ] = d i s [ u ] + v a l u e dis[v]=dis[u]+value dis[v]=dis[u]+value,若设题中所求起点到点 i i i的最短路的数目为 a n s [ i ] ans[i] ans[i],则此时应同时取 a n s [ v ] = a n s [ u ] ans[v]=ans[u] ans[v]=ans[u]。显然这样所有可到达的点 a n s ans ans值都会为 1 1 1,因为每个点只会被第一次更新 d i s dis dis数组的点更新 a n s ans ans数组,所以我们应多进行一次对于 a n s ans ans数组的更新,当 d i s [ v ] = d i s [ u ] + v a l u e dis[v]=dis[u]+value dis[v]=dis[u]+value时,我们应同时更新 a n s [ v ] + = a n s [ u ] ans[v]+=ans[u] ans[v]+=ans[u]。即可在更新最短路的同时更新最短路计数。由于 N N N M M M是在 1 0 6 10^6 106级别的,所以使用堆优化的 D i j k s t r a Dijkstra Dijkstra算法进行最短路求解,这种大数据 S P F A SPFA SPFA可能会被出题人构造的特殊数据卡掉,但是看题解里应该 S P F A SPFA SPFA应该没被卡,有感兴趣的可以自己写写。

#include<bits/stdc++.h>
#define N int(1e6+100)
#define M int(2e6+100)
#define reg register
using namespace std;
const int mod=100003;
struct node{
    int to,nxt;
}edge[M<<1];
struct pnt{
    int d,id;
    pnt(int b, int a){d=a,id=b;}
    bool operator >(const pnt &x) const{
        return x.d>d;
    }
    bool operator <(const pnt &x) const{
        return x.d<d;
    }
};
int head[N],cnt,n,m,u,v,ans[N],dis[N],vis[N];
inline void read(int &x){
    int s=0,w=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){s=(s<<3)+(s<<1)+(ch&15);ch=getchar();}
    x=s*w;
}
inline void addedge(int u, int v){
    edge[++cnt].to=v,edge[cnt].nxt=head[u],head[u]=cnt;
}
inline void superadd(int u, int v){
    addedge(u,v),addedge(v,u);
}
void dijkstra(){
    memset(dis,0x3f3f3f3f,sizeof dis);
    priority_queue<pnt> q;
    dis[1]=0;q.push(pnt(1,0));
    ans[1]=1;
    while(!q.empty()){
        pnt x=q.top();q.pop();
        if(vis[x.id])continue;
        vis[x.id]=1;
        for(reg int i=head[x.id];i;i=edge[i].nxt){
            int v=edge[i].to;
            if(dis[v]>1+dis[x.id])dis[v]=dis[x.id]+1,ans[v]=ans[x.id];
            else if(dis[v]==1+dis[x.id])(ans[v]+=ans[x.id])%=mod;
            if(!vis[v])q.push(pnt(v,dis[v]));
        }
    }
    return ;
}
int main(){
    read(n),read(m);
    for(reg int i=1;i<=m;i++)read(u),read(v),superadd(u,v);
    dijkstra();
    for(reg int i=1;i<=n;i++)printf("%d\n",ans[i]);
}
P1462 通往奥格瑞玛的道路

题面
S o l u t i o n : Solution: Solution:题里说每通过一条道路会扣一个血量,每通过一个城市会扣除费用,那么我们可以把血量看作边权,费用看作点权。题目中求所经过的城市的最大收费最小,很容易想到二分,通过二分法限制城市的最大收费,如果求最短路的过程中碰到一个城市的收费超过了我们所限制的最大收费,则不更新该点,否则正常更新,最后判断如果 d i s [ n ] dis[n] dis[n]不超过初始血量值,则证明该最大收费可行,继续进行二分法。
初始时我们先空走一遍最短路,如果不能到达 n n n那么输出 A F K AFK AFK,然后通过二分答案求得经过城市最大收费的最小值。
注意: 1. 1. 1.判断能否到达 n n n不是判断是否联通,是判断到 n n n的最短路是否小于所给初值
2. 2. 2.题中边权最大为 1 0 9 10^9 109,用 m e m s e t memset memset初始化 d i s dis dis数组时应注意不要使用 0 x 7 f 0x7f 0x7f,会导致爆 i n t int int

#include<bits/stdc++.h>
#define reg register
#define N 10010
#define M 50020
using namespace std;
inline void read(int &x){
    int s=0,w=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){s=(s<<3)+(s<<1)+(ch&15);ch=getchar();}
    x=s*w;
}
struct node{
    int to,val,nxt;
}edge[M<<1];
struct pnt{
    int id,d;
    pnt(int x, int y){
        id=x,d=y;
    }
    bool operator <(const pnt &x) const {
        return x.d<d;
    }
};
int head[N],n,m,cnt,b,vis[N],dis[N],f[N],u,v,w;
inline void addedge(int u, int v, int w){
    edge[++cnt].to=v,edge[cnt].nxt=head[u],head[u]=cnt,edge[cnt].val=w;
}
inline void superadd(int u, int v, int w){
    addedge(u,v,w),addedge(v,u,w);
}
bool dijkstra(int fe){
    if(fe<f[1])return false;
    memset(dis,0x3f,sizeof dis);
    memset(vis,0,sizeof vis);
    priority_queue<pnt> q;
    dis[1]=0;q.push(pnt(1,0));
    while(!q.empty()){
        pnt now=q.top();q.pop();
        if(vis[now.id])continue;
        vis[now.id]=1;
        for(int i=head[now.id];i;i=edge[i].nxt){
            int vv=edge[i].to;
            if(f[vv]<=fe){
                dis[vv]=min(dis[vv],dis[now.id]+edge[i].val);
                if(!vis[vv])q.push(pnt(vv,dis[vv]));
            }
        }
    }
    return dis[n]<=b;
}
int main(){
    read(n),read(m),read(b);
    for(reg int i=1;i<=n;i++)read(f[i]);
    for(reg int i=1;i<=m;i++)read(u),read(v),read(w),superadd(u,v,w);
    int l=1,r=1e9+1,mid=0,ans;
    if(!dijkstra(r)){puts("AFK");return 0;}
    while(l<=r){
        mid=l+r>>1;
        if(dijkstra(mid))r=mid-1,ans=mid;
        else l=mid+1,ans=l;
    }
    cout<<ans<<endl;
}

先发吧,发出来也能更好督促自己更新

U P D 0618 UPD0618 UPD0618

P1522 [USACO2.4] 牛的旅行 Cow Tours

题面
S o l u t i o n : Solution: Solution:题目大意就是一个非连通图,要求在两个不同的连通分量中选两个点加一条边,最后使得图的任意两点之间的最短路中最大的那个最小。
看到 n n n 150 150 150,考虑直接暴力,因为要求所有点之间的最短路,所以选用 f l o y d floyd floyd算法进行求解每个联通块中任意两点的最短路,并预处理出该连通块中最大的最短路。每次枚举两个不同连通块的点,设其为 p 1 , p 2 p_1,p_2 p1,p2,两个连通块只有 p 1 , p 2 p_1,p_2 p1,p2这一条边相连,因此两个连通块合并后 p 1 , p 2 p_1,p_2 p1,p2所在连通块的最大最短路分别为 d i s 1 m a x , d i s 2 m a x dis1_{max},dis2_{max} dis1max,dis2max p 1 , p 2 p_1,p_2 p1,p2在其所在连通块中距离最远的点为 p x , p y p_x,p_y px,py则最终答案 a n s = m i n { a n s , m a x { d i s 1 m a x , d i s 2 m a x , d i s ( p 1 , p 2 ) + d i s ( p x , p 1 ) + d i s ( p y , p 2 ) } } ans=min\{ans,max\{dis1_{max},dis2_{max},dis(p_1,p_2)+dis(p_x,p_1)+dis(p_y,p_2)\}\} ans=min{ans,max{dis1max,dis2max,dis(p1,p2)+dis(px,p1)+dis(py,p2)}}文章来源地址https://www.toymoban.com/news/detail-483657.html

#include<bits/stdc++.h>
#define N 200
#define reg register
using namespace std;
inline void read(int &x){
    int s=0,w=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){s=(s<<3)+(s<<1)+(ch&15);ch=getchar();}
    x=s*w;
}
struct node{
    int x,y;
}p[N];
double di5(node a, node b){
    return sqrt((a.x-b.x)*(a.x-b.x)*1.0+(a.y-b.y)*(a.y-b.y));
}
int n,fa[N];
int find(int x){
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
void merge(int x, int y){
    x=find(x),y=find(y);
    if(x==y)return ;
    fa[y]=x;
}
double sqr[N][N],dis[N][N],mdis[N],sdis[N],ans=1e9;
char chr;
int main(){
    read(n);
    for(reg int i=1;i<=n;i++)read(p[i].x),read(p[i].y),fa[i]=i;
    for(reg int i=1;i<=n;i++){
        for(reg int j=1;j<=n;j++){
            chr=getchar();
            while(chr!='0'&&chr!='1')chr=getchar();
            if(chr=='1')sqr[i][j]=sqr[j][i]=di5(p[i],p[j]),merge(i,j);
        }
    }
    for(reg int i=1;i<=n;i++){
        for(reg int j=1;j<=n;j++){
            if(sqr[i][j])dis[i][j]=sqr[i][j];
            else dis[i][j]=1e9;
            if(i==j)dis[i][j]=0;
        }
    }
    for(reg int k=1;k<=n;k++){
        for(reg int i=1;i<=n;i++){
            for(reg int j=1;j<=n;j++){
                dis[i][j]=min(dis[i][k]+dis[k][j],dis[i][j]);
            }
        }
    }
    for(reg int i=1;i<=n;i++){
        for(reg int j=1;j<=n;j++){
            if(find(i)==find(j))mdis[i]=max(mdis[i],dis[i][j]),sdis[find(i)]=max(sdis[find(i)],dis[i][j]);
        }
    }
    for(reg int i=1;i<=n;i++){
        for(reg int j=1;j<=n;j++){
            if(find(i)!=find(j)){
                ans=min(ans,max(max(mdis[i]+mdis[j]+di5(p[i],p[j]),sdis[find(i)]),sdis[find(j)]));
            }
        }
    }
    printf("%.6lf\n",ans);
}

到了这里,关于洛谷题单 Part 8.2 最短路问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 洛谷题单 -- 图论的简单入门

    图的存储 - 洛谷 这一题要考察图的存储方式 , 一般可以使用邻接矩阵 或 邻接表来存储 图的结点 和1 边的信息 ,详情请看代码 :  【深基18.例3】查找文献 - 洛谷 这题考察有向图的 dfs 和 bfs ,详情请看代码,如果用邻接矩阵的话一定会mle,只能够使用邻接表,我这里采用的是用

    2024年04月13日
    浏览(44)
  • C语言,洛谷题,压缩技术2.0

    题目如下:  这题用C语言实现有一些难度,要用到一个库函数,strcat(头文件是string.h),用于连接两个字符串数组,strcat(str,arr)就是将arr字符数组后面的\\0清除,再将arr字符拼接到str上。 题目指出,输入的是一个n*n大小的输入数据,可以先打印第一行后,计算第一行后,计

    2024年02月07日
    浏览(38)
  • 【题单】一个动态更新的洛谷综合题单

    洛谷试炼场的题目确实很具有代表性,但是近几年以来,又有许多经典题目出现在 OI 界中,这个大题单就是作为洛谷试炼场的扩展和补充。 目录 新版本食用指南 更新日志 题单 Part 0 试机题 Part 1 入门阶段 Part 2 基础算法 Part 3 搜索 Part 4 动态规划 Part 4.1-4.4 动态规划 Part 4.5-

    2024年02月19日
    浏览(33)
  • 洛谷-官方题单版【入门篇】

    题目背景 本题是洛谷的试机题目,可以帮助了解洛谷的使用。 建议完成本题目后继续尝试 P1001、P1008。 另外强烈推荐新用户必读贴 题目描述 超级玛丽是一个非常经典的游戏。请你用字符画的形式输出超级玛丽中的一个场景。 题目描述 输入一个小写字母,输出其对应的大写

    2024年02月02日
    浏览(69)
  • 【DFS专题】深度优先搜索 “暴搜”优质题单推荐 10道题(C++ | 洛谷 | acwing)

    【DFS专题】优质题单推荐 10道题(C++ | 洛谷 | acwing) 来自b站大佬的题单 题单链接 每个位置选什么数 与全排列的差别就是第二个for循环开始的位置,换句话说就是每个数该放什么位置。 参数 : 前u个数 选 or 不选 的 需要保存第x位置的状态的时候就需要用st数组来存状态 i

    2023年04月08日
    浏览(46)
  • 【算法设计与分析基础(第三版)习题答案】8.2 背包问题和记忆功能

    a. 对于下列背包问题的实例,应用自底向上动态规划算法求解。 b. a 中的实例有多少不同的最优子集 c. 一般来说,如何从动态规划算法所生成的表中判断出背包问题的实例是不是具有不止一个最优子集? 承重量 W = 6 物品 重量 价值 1 3 25 2 2 20 3 1 15 4 4 40 5 5 50 题目中要求使用

    2023年04月08日
    浏览(39)
  • 【洛谷】P1576 最小花费(最短路--->最长路(通过改边权变定义))

    分析+变动+ACcode 明确定位最短路,其实就是模板加上稍微改动。 变动位置: 1:把权变成汇率(=1.0),即经过了这条边,前就要乘以这这边权,即乘以汇率,拿肯定汇率越高最后到终点的钱多(一个道理终点钱指定,拿汇率越高,最开始的钱就可以拿的越少) 。我们需要在

    2024年02月15日
    浏览(46)
  • 数据结构学习记录——图-最短路径问题(无权图单源最短路径算法、有权图单源最短路径算法、多源最短路径算法、Dijkstra(迪杰斯特拉)算法、Floyd算法)

    目录 问题分类  无权图单源最短路径算法 思路 伪代码 时间复杂度 代码实现(C语言) 有权图单源最短路径算法 Dijkstra(迪杰斯特拉)算法 伪代码  时间复杂度  代码实现(C语言) 多源最短路径算法 两种方法 Floyd算法 代码实现(C语言) 最短路径问题的抽象 在网络中,求

    2024年02月08日
    浏览(57)
  • 图论与算法(7)最短路径问题

    最短路径问题是指在一个加权图中寻找两个顶点之间的最短路径,其中路径的长度由边的权重确定。 常见的最短路径算法包括: Dijkstra算法 :适用于解决单源最短路径问题,即从一个固定的起点到图中所有其他顶点的最短路径。该算法通过不断选择当前路径上权重最小的顶

    2024年02月06日
    浏览(41)
  • 简短通俗理解动态规划算法--最短路径问题

    问题:从某顶点出发,沿图的边到达另一顶点所经过的路径中,各边上权值之和最小的一条路径——最短路径。在博客动态规划算法中介绍了动态规划的基本思想已经建立动态规划模型的步骤,下面将其中的方法分析最短路径问题。 最短路径有一个重要特性: 如果由起点A经

    2024年02月08日
    浏览(47)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包