1

#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
const int N=100;
struct node{
int v,w;
//点 权
};
vector<node> a[N];//a[i] i:这个顶点相关信息
int n,m;//顶点 边
int dis[N];
int vis[N];
int pre[N];
void Print(int a[],int n,string name){
cout<<name<<":";
for(int i=1;i<=n;i++){
if(a[i] == 0x3f3f3f3f) cout<<"INF ";
else printf("%3d ",a[i]);
}
cout<<"\n"<<"==============\n";
}
void Print_Path(int v){
if(pre[v]==0) cout<<v<<" ";
else{
Print_Path(pre[v]);
cout<<v<<" ";
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int u,v,w;//起点，终点，权
cin>>u>>v>>w;
a[u].push_back(node{v,w});
}
int x=1;
memset(dis,0x3f,sizeof(dis));
dis[x]=0;
Print(dis,n,"dis");
for(int i=1;i<=n;i++){
int tmp=0x3f3f3f3f,id=-1;//找到新的起点
for(int j=1;j<=n;j++){
if(vis[j]==0){
if(dis[j]<tmp){
tmp=min(tmp,dis[j]);
id=j;
}
}
}
vis[id]=1;
//以id作为起点的邻接点，全部尝试更新
for(int j=0;j<a[id].size();j++){
int to=a[id][j].v;
if(dis[id]+a[id][j].w<dis[to]){
dis[to]=dis[id]+a[id][j].w;//松弛
pre[to]=id;//更新前驱点
}
}
Print(dis,n,"dis");//查看dis数组
Print(vis,n,"vis");//查看vis数组
Print(pre,n,"pre");//查看pre数组
// getchar();
}
Print_Path(5);
return 0;
}
/*
5 6
1 2 3
1 3 1
2 3 4
2 4 6
3 5 5
4 5 10
*/