[数据结构与算法]2021pat春 7-4 Recycling of Shared Bicycles (30 分) （dfs 思维

添加链接描述
一条路找最近最小的点

#include<bits/stdc++.h>
using namespace std;
const int N=200+9;
int arr[N];
int dist[N][N],vis[N];
int res=0;
vector<int> ans;
int n,m;
void dfs(int u){
    ans.push_back(u);
    vis[u]=1;
    int t=-1;
    for(int i=1;i<=n;i++){
        if(dist[u][i]!=0x3f3f3f3f&&vis[i]==0&&(t==-1||dist[u][t]>dist[u][i])){
            t=i;
        }
    }
    if(t==-1)return ;
    dfs(t);
}
int main(){
    
    cin>>n>>m;
    memset(dist,0x3f,sizeof dist);
    for(int i=1;i<=n;i++)dist[i][i]=0;
    while(m--){
        int a,b,c;
        cin>>a>>b>>c;
        dist[a][b]=min(dist[a][b],c);
        dist[b][a]=min(dist[b][a],c);
    }
    for(int k=0;k<=n;k++){
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++){
                dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
            }
    }
    dfs(0);
    int flag=0;
    for(int i=0;i<ans.size();i++){
        if(flag==1)cout<<" ";
        cout<<ans[i];
        if(flag)res+=dist[ans[i]][ans[i-1]];
        flag=1;
    }
    cout<<"\n";
    int ok=0;
    for(int i=0;i<=n;i++){
        if(ok==1)cout<<" ";
        if(vis[i]==0)cout<<i,ok=1;
    }
    if(!ok){
        cout<<res;
    }  

    

    return 0;
}