Dijkstra（k不发音）

随便画的

$模板code:$

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2005;
int n, m, s, w[MAXN][MAXN], dis[MAXN]; //dis[i]表示起点到i已知的最短路 
bool flag[MAXN];                       //flag[i]表示i这个点是否已经确定最短路 
void Dijkstra(int s){
    memset(dis, 0x3f, sizeof(dis));
    memset(flag, 0x3f, sizeof(flag));
    dis[s] = 0;
    for(int i = 1; i <= n; i ++){
        int u = 0;
        for(int v = 1; v <= n; v ++){ //找到flag = false的点中，dis最小的点 
            if(!flag[v] && dis[v] < dis[u]) u = v;
        }
        flag[u] = true;
        for(int v = 1; v <= n; v ++){ //松弛其余所有点 
            if(!flag[v] && dis[u] + w[u][v] < dis[v]){
                dis[v] = dis[u] + w[u][v];
            }
        }
    }
}
int main(){
    cin >> n >> m >> s;
    memset(w, 0x3f, sizeof(w));
    for(int i = 1; i <= m; i ++){
        int u, v;
        cin >> u >> v;
        cin >> w[u][v];
    }
    Dijkstra(s);
    for(int i = 1; i <= n; i ++) cout << dis[i] << " ";
    return 0;
}

$>$>$>$>$>$>$>$>$>$>$>$>$>$>$>$>$>$>$>$> $方二$ $<$<$<$<$<$<$<$<$<$<$<$<$<$<$<$<$<$<$<$<$<$<

Bellman_Ford

科普

大佬Orz

$code:$

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1005;  //点 
const int MAXM = 100005;//边
int n, m, u[MAXM], v[MAXM], w[MAXM], dis[MAXM];
void Bellman_Ford(int s){
    memset(dis, 0x3f, sizeof(dis));
    dis[s] = 0;
    for(int i = 1; i < n; i ++){        //n - 1次全图松弛 
        bool flag = false; 
        for(int j = 1; j <= m; j ++){   //全图松弛 
            if(dis[u[j]] + w[j] < dis[v[j]]){
                dis[v[j]] = min(dis[v[j]], dis[u[j]] + w[j]);
                flag = true;
            }
        }
        if(!flag) break;                //小优化：这一次全图松弛没有更新，那么后面不用做了 
    }
    /*      再进行第n次全图松弛，如果还能松弛-->存在负环 
    for(int j = 1; j <= m; j ++)
        if(dis[u[j]] + w[j] < dis[v[j]])
            flag = true;
    */
}
int main(){
    cin >> n >> m >> s;
    for(int i = 1; i <= m; i ++){
        cin >> u[i] >> v[i] >> w[i];
    }
    Bellman_Ford(s);
    for(int i = 1; i <= n; i ++) cout << dis[i] << " ";
    return 0;
}