最短路

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 【模板】单源最短路径（标准版）

堆优化的dijkstra

#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;
	Next[cnt] = head[x];
	head[x] = cnt ;
}
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;
		add(u , v , w);
	}
	diji();
	for(int i = 1; i <= n ; i ++){
		cout << d[i] << " ";
	}
}