• 欢迎光临~

# 最短路

## T1P5318 【深基18.例3】查找文献

dfs和bfs用set存方便排序

``````#include<bits/stdc++.h>
using namespace std;
set<int>a[1000020];
int v[1000020];
int n , m;
void dfs(int x){
if(v[x])return;
v[x] = 1;
cout << x << " ";
for(int y : a[x]){
dfs(y);
}
}
queue<int>q;
void bfs(){
q.push(1);
while(!q.empty()){
int x = q.front();
q.pop();
if(v[x])continue;
v[x] = 1;
cout << x << " ";
for(int y : a[x]){
q.push(y);
}
}
}
int main () {
cin >> n >> m ;
for(int i = 1; i <= m ; i ++){
int x , y;
cin >> x >> y;

a[x].insert(y);
}
dfs(1);
cout << endl;
memset(v , 0 , sizeof v);
bfs();
}
``````

## P3371 【模板】单源最短路径（弱化版）

Floyd模板题

``````#include<bits/stdc++.h>
using namespace std;
int n ,  m ,  s;
int f[5000][5000];
int main () {
cin >> n >> m >> s;
for(int i = 1 ; i <= 1001 ; i ++){
for(int j = 1 ; j <= 1001 ; j ++){
f[i][j] = 1000200;
}
}
for(int i = 1 ; i <= m ; i ++){
int u , v , w ;
cin >> u >> v >> w;
f[u][v] = min(f[u][v] , w);
}
f[s][s] = 0;
for(int k = 1 ; k <= n ; k ++){
for(int i = 1; i <= n ; i ++){
for(int j = 1; j <= n ;j ++){
f[i][j] = min(f[i][j] , f[i][k] + f[k][j]);
}
}
}
for(int i = 1; i <= n ; i ++){
if(f[s][i] == 1000200)cout << "2147483647" << " ";
else cout << f[s][i] << " ";
}
}
``````

## P4779 【模板】单源最短路径（标准版）

``````#include<bits/stdc++.h>
using namespace std ;
int n , m , s;
const int N = 100020;
int head[N] , Next[N] , cnt , edge[N] , ver[N];
int tot ;
void add(int x, int y ,int w){
ver[++cnt] = y;
edge[cnt] = w;
}
int d[N] ;
priority_queue<pair<int , int > > q;
int v[N];
void diji(){
memset(d , 0x3f , sizeof(d) ) ;
d[s] = 0;
q.push(make_pair(-d[s] , s));
while(!q.empty()){
int x = q.top().second ;
q.pop() ;
if(v[x])continue ;
v[x] = 1;
for(int i = head[x] ; i ; i = Next[i]){
int y = ver[i] , z = edge[i];
if(d[y] > d[x] + z){
d[y] = d[x] + z ;
q.push(make_pair(-d[y] , y));
}
}
}
}
int main () {
cin >> n >> m >> s;
for(int i = 1; i <= m ;i ++){
int u , v , w;
cin >> u >> v >> w;