(模板)dijkstra算法

#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 101;
int f[maxn], a[maxn][maxn], d[maxn], path[maxn];
int n, start;
const int inf = 99999;
void (){
	cin >> n >> start;
	int x, y, w;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++){
			if(i == j)
				a[i][j] = 0;
			else
				a[i][j] = inf;
		}
		
		while(cin >> x >> y >> w){
			a[x][y] = a[y][x] = w;
		}
		
}
void dijkstra(int s){
	for(int i=1;i<=n;i++){
		d[i] = a[s][i];
		f[i] = false;
		path[i] = s;
	}
	f[s] = true;
	for(int i=2;i<=n;i++){
		int mind = inf;
		int k = 0;
		for(int j=1;j<=n;j++)
			if(!f[j] && d[j]<mind){
				mind = d[j];
				k = j;
			}
		if(mind == inf)
			break;
		f[k] = true;
		for(int j=1;j<=n;j++)
			if(!f[j] && d[k]+a[k][j]<d[j])
			{
				d[j] = d[k]+a[k][j];
				path[j] = k;
			}
	}
	
}
void dfs(int i){
	if(i != start)
		dfs(path[i]);
	cout << i << " ";
}
void write(){
	cout << start << "到其余各点的最短距离是:"<< endl;
	for(int i=1;i<=n;i++){
		if(i != start){
			if(d[i] == inf)
				cout << i << "不可达";
			else{
				cout << i << "的最短距离：" << d[i] << ",依次经过的点：";
			}
			dfs(path[i]);
			cout << i << endl;
		}
		
	}
}
int main(){
	init();
	dijkstra(start);
	write();
	return 0;
}