什么时候要用弗洛伊德算法

分析一下题目，我们看到数据量只有一百，这个时候我们就要注意是否是要用弗洛伊德算法，然后接着我们还需要枚举每一种情况，我们可以用到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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44