最短路

dijkstra

$O(m \cdot log_m)$

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

const int N = 1e5+50;

int n, m, s;
vector<pair<int,int>>to[N];
int pre[N];// pre[x] 表示 到x的最短路，他的父亲是谁 
int dis[N];
void dijkstra(){
    memset(dis,63,sizeof dis);
    dis[s] = 0 ;
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q;
    q.push({dis[s],s});
    while(!q.empty()){
        int u = q.top().second; int disu = q.top().first; q.pop();
        if(disu > dis[u]) continue;
        for(auto t:to[u]){
            int v = t.first, val = t.second;
            if(dis[v] > dis[u] + val){
                dis[v] = dis[u] + val;
                pre[v] = u;
                q.push({dis[v],v}); 
            }
        }
    }
}
int main(){
    cin >> n >> m >>s;
    for(int i=1;i<=m;i++)
    {
        int u ,v , val;
        cin >> u >> v>> val;
        to[u].push_back({v,val});
    }
    dijkstra();
    for(int i=1;i<=n;i++){
        cout<<dis[i]<<" ";
    }
    vector<int>path;
    while(t != s){
        path.push_back(t);
        t = pre[t];
    }
    path.push_back(s);
    reverse(path.begin(),path.end()); 
    return 0;
}

Floyd

$O(n^3)$

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

int n, m ;
int dis[N][N];
int main(){
    cin >> n >> m;
    memset(dis,63,sizeof dis);
    for(int i=1;i<=m;i++){
        int u , v, val; cin >> u >> v >> val;
        dis[u][v] = dis[v][u] = min(dis[u][v],val);
    } 
    for(int k = 1 ; k <= n; k ++){
        for(int x = 1; x <= n ;x ++){
            for(int y = 1; y<= n ;y ++){
                dis[x][y] = min(dis[x][y],dis[x][k]+dis[k][y]);
            } 
        }
    }
    for(int i=1;i<=n;i++){
        dis[i][i] = 0;
        for(int j =1; j<= n ;j ++){
            cout<<dis[i][j]<<" ";
        }cout<<"\n";
    }

    return 0;
}

拓扑

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

const int N = 110;
int n ;
vector<int>to[N];
int d[N];
int main(){
    cin >> n;
    for(int i=1;i<=n;i++){
        int v ; 
        while(cin >>v){
            if(v == 0)break;
            to[i].push_back(v);
            d[v]++;
        }
    }
    queue<int>q;
    for(int i=1;i<=n;i++){
        if(!d[i]){
            q.push(i);
        }
    }
    vector<int>ans;
    while(!q.empty()){
        int u = q.front();q.pop();
        ans.push_back(u);
        for(auto v:to[u]){
            d[v]--;
            if(!d[v]){
                q.push(v);
            }
        }
    }
    for(auto i:ans){
        cout<<i<<" ";
    }
    return 0;
}

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com