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;
}