AW344 观光之旅

本文主要是介绍AW344 观光之旅，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目地址

---

易错点：

• 如果要将k改为k-1则需要保证全部改完，否则就会出现严重错误.
• 获取最小环时j应当大于i，由对称性可知最终可求出正确答案.
• 环的性质是dis[i][j]+a[j][k]+a[k][i]，即呈环状.
• 需要开long long.

---

#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#define ll long long
using namespace std;
const int MAXN=1e3,MAXM=2e4,INF=0x3f3f3f3f;
vector<int> nowPath;
int pos[MAXN][MAXN];
void getPath(int a,int b){if(!pos[a][b])return;int k=pos[a][b];getPath(a,k);nowPath.push_back(k);getPath(k,b);
}
int a[MAXN][MAXN],dis[MAXN][MAXN];
int main(){memset(a,0x3f,sizeof(a));int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)a[i][i]=0;for(int i=1;i<=m;i++){int u,v,w;scanf("%d%d%d",&u,&v,&w);a[u][v]=a[v][u]=min(w,a[u][v]);}memcpy(dis,a,sizeof(a));int minLength=INF;for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(dis[i][j]>dis[i][k-1]+dis[k-1][j]){dis[i][j]=dis[i][k-1]+dis[k-1][j];pos[i][j]=k-1;}}}for(int i=1;i<=n;i++){if(i!=k)for(int j=i+1;j<=n;j++){if(j!=k){if((ll)dis[i][j]+a[j][k]+a[k][i]<minLength){minLength=dis[i][j]+a[j][k]+a[k][i];nowPath.clear();nowPath.push_back(i);getPath(i,j);nowPath.push_back(j);nowPath.push_back(k);}}}}}if(minLength==INF){printf("No solution.\n");return 0;}for(int i=0;i<nowPath.size();i++){printf("%d ",nowPath.at(i));}printf("\n");return 0;
}

 

这篇关于AW344 观光之旅的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---