复兴提高DAY08最短路（一）

谁来教我C++

2025-07-08 21:13:50

发布于：上海

18阅读

0回复

0点赞

T1单源最短路径1

#include<bits/stdc++.h>
using namespace std;

const int maxn = 1005;

int e[maxn][maxn];
int dis[maxn], vis[maxn];

void dij(int n,int s){
    for(int i = 0;i <= n;i++)
        dis[i] = 1e9;
    dis[s] = 0;
    for(int i = 1;i <= n;i++){
        int u = 0;        
        for(int j = 1;j <= n;j++)
            if(!vis[j] && dis[j] < dis[u]) u = j;
        vis[u] = 1;
        for(int j = 1;j <= n;j++){
            if(e[u][j]) {
                int v = j;
                int w = e[u][j];
                if(dis[v] > dis[u] + w)
                    dis[v] = dis[u] + w;
            }
        }
    }
}


int main(){
    int n,m,s;
    cin >> n >> m >> s;
    for(int i = 0;i < m;i++){
        int u,v,w;
        cin >> u >> v >> w;
        int tmp = e[u][v] ? e[u][v] : 1e9;
        e[u][v] = min(tmp,w);
    }
    dij(n,s);
    for(int i = 1;i <= n;i++){
        if(dis[i] != 1e9) cout << dis[i] << ' ';
        else cout << -1 << ' ';
    }
    return 0;
}

T2无向图的最短路径

#include<bits/stdc++.h>
using namespace std;

const int maxn = 1005;
int n,m;
int e[maxn][maxn];
int dis[maxn], vis[maxn];

void dij(){
    for(int i = 0;i <= n;i++)
        dis[i] = 1e9;
    dis[1] = 0;
    for(int i = 1;i <= n;i++){
        int u = 0;        
        for(int j = 1;j <= n;j++)
            if(!vis[j] && dis[j] < dis[u]) u = j;
        vis[u] = 1;
        for(int j = 1;j <= n;j++){
            if(e[u][j]) {
                int v = j;
                int w = e[u][j];
                if(dis[v] > dis[u] + w)
                    dis[v] = dis[u] + w;
            }
        }
    }
}


int main(){
    cin >> n >> m;
    for(int i = 0;i < m;i++){
        int u,v,w;
        cin >> u >> v >> w;
        int tmp = e[u][v] ? e[u][v] : 1e9;
        e[u][v] = e[v][u] = min(tmp,w);
    }
    dij();
    for(int i = 2;i <= n;i++){
        cout << dis[i] << "\n";
    return 0;
}

T3小码君送信

#include<bits/stdc++.h>
using namespace std;

const int maxn = 2005;

long long e[maxn][maxn];
long long dis[maxn], vis[maxn];

void dij(int n,int s,int off){
    for(int i = 0;i <= 2 * n;i++)   //初始化 dis = inf 
        dis[i] = 1e9;
    dis[s] = 0;                 //起点dis = 0 
    for(int i = 1;i <= n;i++){
        int u = 0;        
        for(int j = 1 + off;j <= n + off;j++)  //找到已有的最短边 
            if(!vis[j] && dis[j] < dis[u]) u = j;
        vis[u] = 1;
        for(int j = 1 + off;j <= n + off;j++){
            if(e[u][j]) {
                int v = j;
                int w = e[u][j];
                if(dis[v] > dis[u] + w)  //松弛操作 
                    dis[v] = dis[u] + w;
            }
        }
    }
}

int main(){
    int n,m;
    cin >> n >> m;
    for(int i = 0;i < m;i++){
        int u,v,w;
        cin >> u >> v >> w;
        int tmp = e[u][v] ? e[u][v] : 1e9; //注意可能出现重边，所以要保留最短边 
        e[u][v] = min(tmp,w);
        e[v + n][u + n] = min(tmp,w); 
    }
    dij(n,1,0);     //正着跑最短路 
    long long ans = 0;
    for(int i = 2;i <= n;i++){
        ans += dis[i];
    }
    dij(n,n + 1,n);  //跑反图的最短路 
    for(int i = 2 + n;i <= n + n;i++){
        ans += dis[i];
    }
    cout << ans;
    return 0;
}

有帮助，赞一个

去预览

0/2000

这里空空如也

热门讨论