最短路入门板子及各自题目

Source

单源最短路

朴素Dijkstra求最短路(O(n^2))

题目链接
给定一个 n 个点 m 条边的有向图,图中可能存在重边和自环,所有边权均为正值

请你求出 1 号点到 n 号点的最短距离,如果无法从 1 号点走到 n 号点,则输出 −1。

输入格式
第一行包含整数 n 和 m。

接下来 m 行每行包含三个整数 x,y,z,表示存在一条从点 x 到点 y 的有向边,边长为 z。

输出格式
输出一个整数,表示 1 号点到 n 号点的最短距离。

如果路径不存在,则输出 −1。

数据范围
1≤n≤500,
1≤m≤105,
图中涉及边长均不超过10000。

输入样例:
3 3
1 2 2
2 3 1
1 3 4
输出样例:
3

#include<bits/stdc++.h>
using namespace std;
const int N=510;
int g[N][N];
int dis[N];
int st[N];
int n,m;
int dijkstra(){
    
      
    memset(dis,0x3f,sizeof dis);
    dis[1]=0;
    for(int i=1;i<=n;i++){
    
      
        int t=0;
        for(int j=1;j<=n;j++){
    
      
            if(!st[j]&&(dis[t]>dis[j])) t=j;
        }
        st[t]=true;
        for(int j=1;j<=n;j++){
    
      
            dis[j]=min(dis[j],dis[t]+g[t][j]);
        }
    }
    if(dis[n]==0x3f3f3f3f) return -1;
    return dis[n];
}
int main(){
    
      
    memset(g,0x3f,sizeof g);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
    
      
        int u,v,c;
        cin>>u>>v>>c;
        g[u][v]=min(g[u][v],c);
    }
    int t=dijkstra();
    cout<<t<<endl;     
    
    return 0;
}

堆优化版Dijkstra求最短路(O(mlogn))

题目链接
给定一个 n 个点 m 条边的有向图,图中可能存在重边和自环,所有边权均为非负值

请你求出 1 号点到 n 号点的最短距离,如果无法从 1 号点走到 n 号点,则输出 −1。

输入格式
第一行包含整数 n 和 m。

接下来 m 行每行包含三个整数 x,y,z,表示存在一条从点 x 到点 y 的有向边,边长为 z。

输出格式
输出一个整数,表示 1 号点到 n 号点的最短距离。

如果路径不存在,则输出 −1。

数据范围
1≤n,m≤1.5×105,
图中涉及边长均不小于 0,且不超过 10000。

输入样例:
3 3
1 2 2
2 3 1
1 3 4
输出样例:
3

#include<bits/stdc++.h>
using namespace std;
const int N=150010;
typedef pair<int,int> pr;
priority_queue<pr, vector<pr>, greater<pr> >q;
int head[N],ne[N],val[N],e[N],idx=0;
int dis[N];
bool st[N];
int n,m;
void add(int a,int b,int c){
    
      
    val[idx]=c;
    e[idx]=b;
    ne[idx]=head[a];
    head[a]=idx;
    idx++;
}
void init(){
    
      
    memset(head,-1,sizeof head);
}
int dijkstra(){
    
      
    memset(dis,0x3f,sizeof dis);
    dis[1]=0;
    q.push({
    
      0,1});
    while(q.size()){
    
      
        auto t=q.top();q.pop();
        int dist=t.first,id=t.second;
        if(st[id]) continue;//如果更新过这个编号,就continue掉,降低复杂度
        st[id]=true;
        for(int i=head[id];i!=-1;i=ne[i]){
    
      
            int temp=e[i];
            if(dis[temp]>dist+val[i]){
    
      
                dis[temp]=dist+val[i];
                q.push({
    
      dis[temp],temp});
            }
        }
    }
    if(dis[n]==0x3f3f3f3f) return -1;
    return dis[n];
}

int main(){
    
      
    init();

    cin>>n>>m;  
    for(int i=1;i<=m;i++){
    
      
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
    }

    int t=dijkstra();
    cout<<t<<endl;

    return 0;
}

有边数限制的最短路(Bellman_Ford)(O(nm))

题目链接
给定一个 n 个点 m 条边的有向图,图中可能存在重边和自环, 边权可能为负数。

请你求出从 1 号点到 n 号点的最多经过 k 条边的最短距离,如果无法从 1 号点走到 n 号点,输出 impossible。

注意:图中可能 存在负权回路 。

输入格式
第一行包含三个整数 n,m,k。

接下来 m 行,每行包含三个整数 x,y,z,表示存在一条从点 x 到点 y 的有向边,边长为 z。

输出格式
输出一个整数,表示从 1 号点到 n 号点的最多经过 k 条边的最短距离。

如果不存在满足条件的路径,则输出 impossible。

数据范围
1≤n,k≤500,
1≤m≤10000,
任意边长的绝对值不超过 10000。

输入样例:
3 3 1
1 2 1
2 3 1
1 3 3
输出样例:
3

#include<bits/stdc++.h>
using namespace std;
const int N=510,M=10010;
struct node{
    
      
    int a;
    int b;
    int w;
}edge[M];
int n,m,k,flag;
int dis[N],backup[N];
int bellman_ford(){
    
      
    memset(dis,0x3f,sizeof dis);
    dis[1]=0;
    for(int i=1;i<=k;i++){
    
      //k次更新 (最多k条边)
        memcpy(backup,dis,sizeof dis);//每次更新都往前 “ 准确  ”更新,用上一次的值,来更新这一次的距离 
        for(int j=1;j<=m;j++){
    
      
            int a=edge[j].a,b=edge[j].b,w=edge[j].w;
            dis[b]=min(dis[b],backup[a]+w);
        }
    }
    /*
    k=1
    1 2 1  j=1
    2 3 1  j=2
    1 3 3  j=3
    j==1 {
        dis[2]= min(dis[2],dis[1]+w) =min(inf,0+1)=1;
    }
    j==2{
        dis[3]= min(dis[3],dis[2]+w) =min(inf,1+1)=2;
    }
    j==3{
        dis[3]= min(dis[3],dis[1]+w) =min(2,0+3)=2;
    }
    所以到3的距离由于发生串联 结果不正确 

    k=1
    1 2 1  j=1
    2 3 1  j=2
    1 3 3  j=3
    j==1 {
        dis[2]= min(dis[2],backup[1]+w) =min(inf,0+1)=1;
    }
    j==2{
        dis[3]= min(dis[3],backup[2]+w) =min(inf,inf+1)=inf;
    }
    j==3{
        dis[3]= min(dis[3],dis[1]+w) =min(inf,0+3)=3;
    }

    */
    if(dis[n]>0x3f3f3f3f/2) return -1;
    flag=1;//避免最短路径为-1的时候的情况 
    return dis[n];
}
int main(){
    
      
    cin>>n>>m>>k;
    for(int i=1;i<=m;i++){
    
      
        int a,b,w;
        cin>>a>>b>>w;
        edge[i].a=a,edge[i].b=b,edge[i].w=w;
    }
    flag=0;
    int t=bellman_ford();
    if(t==-1&&!flag) cout<<"impossible"<<endl;
    else cout<<t<<endl;

    return 0;
} 

spfa求最短路(一般O(m),最坏(O(nm)))

题目链接
给定一个 n 个点 m 条边的有向图,图中可能存在重边和自环, 边权可能为负数。

请你求出 1 号点到 n 号点的最短距离,如果无法从 1 号点走到 n 号点,则输出 impossible。

数据保证不存在负权回路。

输入格式
第一行包含整数 n 和 m。

接下来 m 行每行包含三个整数 x,y,z,表示存在一条从点 x 到点 y 的有向边,边长为 z。

输出格式
输出一个整数,表示 1 号点到 n 号点的最短距离。

如果路径不存在,则输出 impossible。

数据范围
1≤n,m≤105,
图中涉及边长绝对值均不超过 10000。

输入样例:
3 3
1 2 5
2 3 -3
1 3 4
输出样例:
2

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int head[N],ne[N],e[N],len[N],idx=0;
int dis[N],n,m;
bool st[N],flag;
void add(int a,int b,int z){
    
      
    len[idx]=z;
    e[idx]=b;
    ne[idx]=head[a];
    head[a]=idx;
    idx++;
}
int spfa(){
    
      

    memset(dis,0x3f,sizeof dis);
    dis[1]=0;

    queue<int>q;
    q.push(1);
    st[1]=true;
    while(q.size()){
    
      
        int p=q.front();q.pop();    
        st[p]=false;
        for(int i=head[p];i!=-1;i=ne[i]){
    
      
            int id=e[i];
            if(dis[id]>dis[p]+len[i]){
    
      
                dis[id]=dis[p]+len[i];
                if(!st[id]){
    
      
                    q.push(id);
                    st[id]=true;
                }
            }
        }       
    }

    if(dis[n]==0x3f3f3f3f) return -1;
    flag=true;
    return dis[n]; 

}
void init(){
    
      
    memset(head,-1,sizeof head);
}
int main(){
    
      
    init();
    cin>>n>>m;
    for(int i=1;i<=m;i++){
    
      
        int a,b,z;
        cin>>a>>b>>z;
        add(a,b,z);
    }
    flag=false;
    int t=spfa();
    if(t==-1&&!flag) cout<<"impossible"<<endl;
    else cout<<t<<endl;

    return 0;
} 

spfa判断负环

题目链接
给定一个 n 个点 m 条边的有向图,图中可能存在重边和自环, 边权可能为负数。

请你判断图中是否存在负权回路。

输入格式
第一行包含整数 n 和 m。

接下来 m 行每行包含三个整数 x,y,z,表示存在一条从点 x 到点 y 的有向边,边长为 z。

输出格式
如果图中存在负权回路,则输出 Yes,否则输出 No。

数据范围
1≤n≤2000,
1≤m≤10000,
图中涉及边长绝对值均不超过 10000。

输入样例:
3 3
1 2 -1
2 3 4
3 1 -4
输出样例:
Yes

#include<bits/stdc++.h>
using namespace std;
const int N=10010;
int e[N],head[N],ne[N],len[N],idx=0;
int dis[N],cnt[N],n,m;
bool st[N];
void add(int a,int b,int z){
    
      
    len[idx]=z;
    e[idx]=b;
    ne[idx]=head[a];
    head[a]=idx;
    idx++;
}
void init(){
    
      
    memset(head,-1,sizeof head);
}
bool spfa(){
    
      
    queue<int>q;
    for(int i=1;i<=n;i++) {
    
      
        st[i]=true;//因为从起点不一定能到达负环那个位置,所以我们存所有点,这样保证只要有负环就一定能查到
        q.push(i);
    }

    while(q.size()){
    
      
        int id=q.front();q.pop();
        st[id]=false;
        for(int i=head[id];i!=-1;i=ne[i]){
    
      
            int j=e[i];
            if(dis[j]>dis[id]+len[i]){
    
      
                dis[j]=dis[id]+len[i];
                cnt[j]=cnt[id]+1;//核心就是用cnt数组记录已经走过的变得条数,如果if为真,那么我到这个点的边数就是,到id点的边数+  id->j这一点的一条边,就是cnt[j]=cnt[id]+1;
                if(cnt[j]>=n) return true;//边数有n条 所以点数至少有n+1个,但最多有n个点,所以根据抽屉原理,肯定有一个重新走到的点,即形成一个回路(我们根据边数变小来更新下一个点,既然又走回这个点了,说明这一段路是负权回路) 
                if(!st[j]){
    
      
                    q.push(j);
                    st[j]=true;                 
                }
            }
        }
    }
    return false;
}
int main(){
    
      
    init();
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++){
    
      
        int a,b,c;
        scanf("%d %d %d",&a,&b,&c);
        add(a,b,c);
    }

    bool flag=spfa();
    if(flag) puts("Yes");//cout<<"Yes"<<endl;
    else puts("No");//cout<<"No"<<endl;

    return 0;
}

后记

Dijkstra只能用于处理正权边,而spfa可以处理负权边

多源汇最短路

Floyd求最短路(O(n^3))

题目链接
给定一个 n 个点 m 条边的有向图,图中可能存在重边和自环,边权可能为负数。

再给定 k 个询问,每个询问包含两个整数 x 和 y,表示查询从点 x 到点 y 的最短距离,如果路径不存在,则输出 impossible。

数据保证图中不存在负权回路。

输入格式
第一行包含三个整数 n,m,k。

接下来 m 行,每行包含三个整数 x,y,z,表示存在一条从点 x 到点 y 的有向边,边长为 z。

接下来 k 行,每行包含两个整数 x,y,表示询问点 x 到点 y 的最短距离。

输出格式
共 k 行,每行输出一个整数,表示询问的结果,若询问两点间不存在路径,则输出 impossible。

数据范围
1≤n≤200,
1≤k≤n2
1≤m≤20000,
图中涉及边长绝对值均不超过 10000。

输入样例:
3 3 2
1 2 1
2 3 2
1 3 1
2 1
1 3
输出样例:
impossible
1

#include<bits/stdc++.h>
using namespace std;
const int inf=1e9;
const int N=210;
int dis[N][N],n,m,q;
void floyd(){
    
      
    for(int k=1;k<=n;k++){
    
      
        for(int i=1;i<=n;i++){
    
      
            for(int j=1;j<=n;j++){
    
      
                dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
                /*检查Dis(i,k) + Dis(k,j) < Dis(i,j)是否成立,如果成立,证明从i到k再到j的路径比i直接到j的路径短,我们便设置Dis(i,j) = Dis(i,k) + Dis(k,j),这样一来,当我们遍历完所有节点k,Dis(i,j)中记录的便是i到j的最短路径的距离。*/
            }
        }
    }
}
int main(){
    
      
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++){
    
      
        for(int j=1;j<=n;j++){
    
      
            if(i==j) dis[i][j]=0;
            else dis[i][j]=inf;
        }
    }
    for(int i=1;i<=m;i++){
    
      
        int x,y,z;
        cin>>x>>y>>z;
        dis[x][y]=min(dis[x][y],z);
    }

    floyd();

    for(int i=1;i<=q;i++){
    
      
        int x,y;
        cin>>x>>y;//if判断>inf/2是因为由于可能存在负权边,所以无通路情况可能是比inf小 比如 正无穷+10 还是正无穷但是并不是原来的正无穷了
        if(dis[x][y]>inf/2) cout<<"impossible"<<endl;
        else cout<<dis[x][y]<<endl;
    }

    return 0;
}

练习题(持续更新)

简单单源最短路径问题