保研机试训练Day-12

单源最短路算法

朴素Dijkstra求最短路

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为正值。请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 −1。

#include<bits/stdc++.h>
using namespace std;
const int N = 510;
const int INF = 10005;
int g[N][N];
int dis[N];
bool st[N];
int n,m;
int dijkstra(){
    // memset(dis,INF,sizeof dis);
    for(int j=1;j<=n;j++){
        dis[j] = INF;
    }
    dis[1] = 0;
    for(int i=0;i<n;i++){
        int t = 0;
        for(int j=1;j<=n;j++){
            if(!st[j] && (t == 0 || 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] == INF) return -1;
    else return dis[n];
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            g[i][j] = INF;
    // memset(g,INF,sizeof g);
    while(m--){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        g[a][b] = min(g[a][b],c);
    }
    int ans = dijkstra();
    printf("%d\n",ans);
    return 0;
}

堆优化Dijkstra求最短路

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环。

所有边的长度都是 1，点的编号为 1∼n。

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

#include<bits/stdc++.h>
using namespace std;
const int N = 150010;

typedef pair<int,int> PII;
// 稀疏图用邻接表来存
int h[N], e[N], ne[N], idx;
int w[N]; // 用来存权重
int dis[N];
bool st[N]; // 如果为true说明这个点的最短路径已经确定
int n,m;

void add(int a,int b,int c){
    // 有重边也不要紧，假设1->2有权重为2和3的边，再遍历到点1的时候2号点的距离会更新两次放入堆中
    // 这样堆中会有很多冗余的点，但是在弹出的时候还是会弹出最小值2+x（x为之前确定的最短路径），
    // 并标记st为true，所以下一次弹出3+x会continue不会向下执行。
    e[idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx++;
}

int dijkstra(){
    memset(dis, 0x3f, sizeof dis);
    dis[1] = 0;
  
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    // 这里heap中为什么要存pair呢，首先小根堆是根据距离来排的，所以有一个变量要是距离，
    // 其次在从堆中拿出来的时候要知道知道这个点是哪个点，不然怎么更新邻接点呢？所以第二个变量要存点。
    heap.push({0,1});
  
    while(heap.size()){
        auto t = heap.top();
        heap.pop();
  
        int ver = t.second, distance = t.first;
        if(st[ver]) continue;
        st[ver] = true;
  
        for(int i = h[ver]; i != -1; i = ne[i]){
            int j = e[i];
            if(dis[j] > distance + w[i]){
                dis[j] = distance + w[i];
                heap.push({dis[j], j});
            }
        }
    }
    if(dis[n] == 0x3f3f3f3f) return -1;
    else return dis[n];
}
int main(){
    scanf("%d%d",&n,&m);
  
    memset(h, -1, sizeof h);
  
    while(m--){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
    }
  
    int ans = dijkstra();
    printf("%d\n",ans);
    return 0;
}

单源最短路

单源最短路算法

朴素Dijkstra求最短路

堆优化Dijkstra求最短路

CATALOG

FEATURED TAGS