什么时候要用弗洛伊德算法
分析一下题目，我们看到数据量只有一百，这个时候我们就要注意是否是要用弗洛伊德算法，然后接着我们还需要枚举每一种情况，我们可以用到next_permutation这个方法
#include<bits/stdc++.h>
using namespace std;
const int N = 105;
int dp[N][N];
int n;
int p;
int a[15];
int main(){
cin >> n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin >> dp[i][j];
}
}
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
dp[i][j] = min(dp[i][j],dp[i][k]+dp[k][j]);
}
}
}
cin >> p;
for(int i=1;i<=p;i++){
cin >> a[i];
}
sort(a+1,a+1+p);
int ans = 0x7fffffff;
if(p==0){
cout << dp[1][n];
return 0;
}
do{
int sum = dp[1][a[1]] + dp[a[p]][n];
for(int i=1;i<=p-1;i++){
sum += dp[a[i]][a[i+1]];
}
ans = min(ans,sum);
}while(next_permutation(a+1,a+1+p));
cout << ans;
return 0;
}
原文地址：https://blog.csdn.net/wniuniu_/article/details/140400985
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！