单源最短路

算法模型

  • 边权均为正 Dijkstra
  • 有负边权 spfa
  • 模板
//堆优化Dijkstra O(mlogn)
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;

const int N=2510,M=6210,inf=0x3f3f3f3f;
int n,m,cnt,st,ed,head[N],dis[N];
bool vis[N];

struct edge{
    int v,w,ne;
}e[M*2];

struct node{
    int id,dis;
    inline bool operator < (const node &x) const{
        return dis>x.dis;
    }
};
priority_queue <node> q;

inline void add(int u,int v,int w){
    e[++cnt].v=v;
    e[cnt].w=w;
    e[cnt].ne=head[u];
    head[u]=cnt;
}

void Dijkstra(){
    memset(dis,inf,sizeof dis);
    dis[st]=0;
    q.push((node) {st,0});
    while(!q.empty()){
        node a=q.top();
        q.pop();
        int u=a.id;
        vis[u]=true;
        for(int i=head[u];i;i=e[i].ne){
            int v=e[i].v;
            if(vis[v]) continue;
            if(dis[v]>dis[u]+e[i].w){
                dis[v]=dis[u]+e[i].w;
                q.push((node) {v,dis[v]});
            }
        }
    }
}

int main(){
    scanf("%d%d%d%d",&n,&m,&st,&ed);
    for(int i=1;i<=m;++i){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w),add(v,u,w);
    }
    Dijkstra();
    printf("%d",dis[ed]);
    return 0;
}

题目

  • 信使
    抽象模型：给出一张图，求从起点开始经过每个点至少一次的最长时间
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;

const int N=1010*2,inf=0x3f3f3f3f;
int n,m,cnt,head[N],dis[N];
bool st[N];//st数组表示某个点当前是否被加入队列中

struct edge{
    int v,w,ne;
}e[N*2];

queue <int> q;

inline void add(int u,int v,int w){
    e[++cnt].v=v;
    e[cnt].w=w;
    e[cnt].ne=head[u];
    head[u]=cnt;
}

int spfa(){
    memset(dis,0x3f,sizeof dis);
    dis[1]=0;
    q.push(1);
    st[1]=true;
    while(!q.empty()){
        int x=q.front();
        q.pop();
        st[x]=false;
        for(int i=head[x];i;i=e[i].ne){
            int v=e[i].v;
            if(dis[v]>dis[x]+e[i].w){
                dis[v]=dis[x]+e[i].w;
                if(!st[v]){
                    st[v]=true;
                    q.push(v);
                }
            }
        }
    }
    for(int i=1;i<=n;++i)
        if(dis[i]==inf) return -1;
    return 1;
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w),add(v,u,w);
    }
    if(spfa()==-1) printf("-1");
    else{
        int maxn=0;
        for(int i=1;i<=n;++i)
            if(dis[i]>maxn) maxn=dis[i];
        printf("%d",maxn);
    }
    return 0;
}
  • 昂贵的聘礼
    题目大意：给定n个点，每个点可以直接到达，或者通过其它点间接到达，且经过某个点i后，与i的等级差的绝对值大于m的点就不能经过，求一条到达1号点的最短路径
    思路：
    1.建图：间接购买可以直接将两个点相连，可如何表示直接购买一个物品？，想到可以建立一个虚拟原点0，由0向各个点连边即可表示直接购买某个物品
    2.等级关系：考虑到1号点必须经过，可以枚举所有包含1号点的区间
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int N=110,inf=0x3f3f3f3f;
int n,m,level[N],dis[N],w[N][N];
bool st[N];

int dijkstra(int l,int r){
    memset(dis,0x3f,sizeof dis);
    memset(st,false,sizeof st);
    dis[0]=0;
    for(int i=1;i<=n;++i){
        int t=-1;
        for(int j=0;j<=n;++j)
            if(!st[j]&&(t==-1||dis[j]<dis[t]))
                t=j;
        st[t]=true;
        for(int j=1;j<=n;++j)
            if(level[j]>=l&&level[j]<=r&&dis[t]+w[t][j]<dis[j])
                dis[j]=dis[t]+w[t][j];
    }
    return dis[1];
}

int main(){
    scanf("%d%d",&m,&n);
    memset(w,0x3f,sizeof w);
    for(int i=1;i<=n;++i){
        int price,cnt;
        scanf("%d%d%d",&price,&level[i],&cnt);
        w[0][i]=price;
        for(int j=1;j<=cnt;++j){
            int t,p;
            scanf("%d%d",&t,&p);
            w[t][i]=p;
        }
    }
    int res=inf;
    for(int i=level[1]-m;i<=level[1];++i) res=min(res,dijkstra(i,i+m));
    printf("%d",res);
    
    return 0;
}
  • 新年好
    思路：
    1.确定5个亲戚的拜访顺序
    2.从佳佳家到亲戚家与亲戚之间家均走最短路
    若做题顺序为1->2 则时间复杂度为O(5!*mlogn)
    2->1 即先预处理出佳佳家与亲戚家到各点的最短路 复杂度为O (mlogn+5!)
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;

const int N=500500,inf=0x3f3f3f3f;
int n,m,cnt,minn,head[N],dis[N],source[N],d[6][N];
bool vis[N],st[N];

struct edge{
    int v,w,ne;
}e[N];

struct node{
    int id,dis;
    inline bool operator < (const node &x) const{
        return dis>x.dis;
    }
};


inline void add(int u,int v,int w){
    e[++cnt].v=v;
    e[cnt].w=w;
    e[cnt].ne=head[u];
    head[u]=cnt;
}

void dijkstra(int x,int st){
    memset(dis,0x3f,sizeof dis);
    memset(vis,false,sizeof vis);
    dis[st]=0;
    priority_queue <node> q;
    q.push((node) {st,0});
    while(!q.empty()){
        node a=q.top();
        q.pop();
        int u=a.id;
        if(vis[u]) continue;
        vis[u]=true;
        for(int i=head[u];i;i=e[i].ne){
            int v=e[i].v;
            if(dis[v]>dis[u]+e[i].w){
                dis[v]=dis[u]+e[i].w;
                q.push((node) {v,dis[v]});
            }
        }
    }
    for(int i=1;i<=n;++i)
        d[x][i]=dis[i];
}

int dfs(int dep,int start,int distance){
    if(dep==6) return distance;
    int res=inf;//res表示每个分支均取最小值
    for(int i=1;i<=5;++i){
        if(!st[i]){
            st[i]=true;     
            res=min(res,dfs(dep+1,i,distance+d[start][source[i]]));
            st[i]=false;
        }
    }
    return res;
}

int main(){
    scanf("%d%d",&n,&m);
    source[0]=1;
    for(int i=1;i<=5;++i)
        scanf("%d",&source[i]);
    for(int i=1;i<=m;++i){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w),add(v,u,w);
    }
    for(int i=0;i<=5;++i)
        dijkstra(i,source[i]);
    printf("%d",dfs(1,0,0));
    return 0;
}
  1. 由题意可以将此题转化为二分答案
    主要是check函数的写法 即如何判断答案是否合法
    只需看当前枚举的答案是否是第k+1小即可
    那么可以将比当前答案大的边的边权赋为1，小的赋为0，跑一边最短路
    至于为什么要跑最短路
    我们的判定为合法的条件是 存在一条大于mid（枚举的答案）的边少于k条
    如果最小的都大于k条，那么不可能存在
    如果最小的不大于k条，那么至少存在一条（最小的这条）
  2. 通过枚举的答案与大于k的边数的关系可以确定二分的修改区间操作
    枚举的答案增大 大于k的边数减少
  3. 把右边界设置为最大值+1，可以判断不连通导致无解的情况
  4. 注意0-1图中可用deque跑最短路
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <deque>
using namespace std;

const int N=1010,inf=0x3f3f3f3f;
int n,m,k;
int dis[N],vis[N],g[N][N],map[N][N];
deque <int> q;

int bfs()
{
    memset(dis,0x3f,sizeof dis);
    memset(vis,0,sizeof vis);
    q.push_back(1); dis[1]=0;
    //一个点会被入队多次 最短距离被更新多次 而只用它更新别的点一次
    while(!q.empty()){
        int x=q.front();
        q.pop_front();
        if(vis[x]) continue;
        vis[x]=1; 
        for(int i=1;i<=n;++i){
            if(map[x][i]==1){
                if(dis[i]>dis[x]+map[x][i]){
                    q.push_back(i);
                    dis[i]=dis[x]+map[x][i];
                }
            }
            else if(map[x][i]==0){
                if(dis[i]>dis[x]){
                    q.push_front(i);
                    dis[i]=dis[x];
                }
            }
        }
    }
    if(dis[n]>k) return 0;
    return 1;
}

bool check(int x)
{
    memset(map,-1,sizeof map);
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
            if(g[i][j])
            {
                if(g[i][j]>x) map[i][j]=1;
                else map[i][j]=0;   
            }
    int res=bfs();
    if(!res) return false;
    return true;
}

int main(){
    scanf("%d%d%d",&n,&m,&k);
    int maxn=0;
    for(int i=1;i<=m;++i){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        g[u][v]=w,g[v][u]=w;
        maxn=max(maxn,w);
    }
    int l=0,r=maxn+1;
    while(l<r){
        int mid=(l+r)>>1;
        //cout<<mid<<endl;
        if(check(mid)) r=mid;
        else l=mid+1;
    }
    if(l==maxn+1) printf("-1");
    else printf("%d",l);
    return 0;
}
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成，浏览时请结合常识与多方信息审慎甄别。
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

友情链接更多精彩内容