最短路【Dijkstra算法模板】
2023-08-19 15:43:00
发布于：浙江
33阅读
0回复
0点赞
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <cmath>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
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;
}
全部评论 15
ḑ̡̖̝͈̯̘͈̱̬̣̝͈͔͕͓̳̱̗̙̃͒̇ͪ̄ͥ̋̈ͬ̌͞ͅl̢͈̣̯̯̯̘̩̹̱̣̣ͦ̂ͣ̅̒ͪͤͮ͛͜ςj̛͆̃͗̑ͩ̏ͮ̋͐̾̆ͫͧ͌̓͏͡͏̸̩̻͇̙͎̞̭̪͚̩͖̪͔l̛͛ͯͧͩš̴̓̈́̆̆̃͑͋̂̎ͤ̔̅ͥ͒͑͏̵̢̘̱̫̯͓̲͚̫̻̞̣̦̹̼̺̺̩d̡ͯͭͣͪ̓̒̏ͮ́̋ͭ͛̐ͧ́͝͏̵͇͇̦͔̩̻l̵̶̢̠͍͈̤̱͔̫̝͔̭̻͈̱͍̠͉̞̙̠̦̥̳̜̤̫͉̱͔̭͎͓̘̝̦̝̹
2023-08-19 来自 浙江
0
有帮助，赞一个