11 条题解
-
2
// https://dashoj.com/p/80 #include <bits/stdc++.h> #define N 50 using namespace std; typedef long long ll; int n, g[N][N], e; // bool gb[N]; ll ans = 0x3f3f3f3f; void dfs(int x, int a, ll an) { if (a == e) { ans = min(an + g[x][n], ans); return; } for (int i = 2; i <= e; i++) { if (i == x) continue; if (!gb[i]) continue; gb[i] = false; if (an + g[x][i] < ans) dfs(i, a + 1, an + g[x][i]); gb[i] = true; } } int main() { ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr); // fill(&gb[0], &gb[0] + N, true); // cin >> n; // e = n - 1; // gb[1] = false; for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) cin >> g[i][j]; // dfs(1, 1, 0); // cout << ans << endl; // return 0; } -
2
开O2优化可以用dfsAC
#include <bits/stdc++.h> using namespace std; typedef long long LL; const int N = 21; int n; int d[N][N]; bool st[N]; LL ans = 0x3f3f3f3f; void dfs(int u, int cnt, LL cost)// 当前所在岛屿， 总共经过了多少个岛屿， 经过cnt个岛屿的花费 { if(cost > ans) return; if (cnt == n && u == n) { ans = min(ans, cost); return; } for (int i = 1; i <= n; i++) { if (i == u) continue; if (st[i]) continue; if (d[u][i] >= ans) continue; st[i] = true; dfs(i, cnt + 1, cost + d[u][i]); st[i] = false; } } void solve() { cin >> n; for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) cin >> d[i][j]; st[1] = true; dfs(1, 1, 0); } int main() { solve(); cout << ans << endl; return 0; } -
1
// Created by ERGO_V on 2025/3/27. #include <bits/stdc++.h> using namespace std; int N; int matrix[17][17]; int vis[17]; int visland[17]; int minTime = 0; bool flag = false; void dfs(long time, int step, int current){ if(step + 1 == N){ if(flag == true && time + matrix[current][N] >= minTime){ return; } else{ minTime = matrix[current][N] + time; flag = true; } } for(int i = 2; i < N; i ++){ if(!vis[i]){ if(flag == true && time + matrix[current][i] >= minTime){ continue; } if(i == current)continue; vis[i] = 1; dfs(time + matrix[current][i], step + 1, i); vis[i] = 0; } } } int main(){ ios::sync_with_stdio(false), cin.tie(nullptr),cout.tie(nullptr); cin >> N; for(int i = 1; i <=N; i ++){ for(int j = 1; j <= N; j++){ cin >> matrix[i][j]; } } memset(vis, 0, sizeof(vis)); dfs(0, 1, 1); cout << minTime << endl; return 0; } -
1
#include<bits/stdc++.h> using namespace std; int n;int mp[20][20]; bool vis[20]; using ll=long long; ll ans=1e9+5; void dfs(int x,ll ann){//x是到了哪座岛出发，ann是花费 if(x==n){ for(int i=1;i<n;i++){ if(!vis[i])return; } ans=min(ans,ann); return; } if(ann>ans){ return; } for(int j=1;j<=n;j++){ if(x==j) continue; if(vis[j]) continue; vis[j]=true; dfs(j,ann+mp[x][j]); vis[j]=false; } } int main(){ cin>>n; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ cin>>mp[i][j]; } } vis[1]=true; dfs(1,0); cout<<ans<<endl; return 0; } -
0
#include <bits/stdc++.h> using namespace std; const int N=20; int n,ans=1e9; int g[N][N]; int st[N],a[N]; //a[]表示当前第n个到达的岛屿的编号 //当前按顺序到达了第x个岛屿，累计的时间 void dfs(int x,int sum){ if(sum>ans) return; if(x==n-1){ ans=min(ans,sum+g[a[x]][n]); //cout<<ans<<endl; return; } for(int i=1;i<n;i++){ if(!st[i]){ st[i]=1; a[x+1]=i; dfs(x+1,sum+g[a[x]][i]); st[i]=0; a[x+1]=0; } } } int main(){ cin>>n; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ cin>>g[i][j]; } } st[1]=1; a[1]=1; dfs(1,0); cout<<ans<<endl; return 0; } -
0
#include<bits/stdc++.h> using namespace std; #define int long long const int inf=2e7+10; int n,vis[20],dis[20][20],ans=inf,sum; void dfs(int now,int step){ int flag=0; if(stepn-1){ if(sum<ans){ ans=sum; } return; } for(int i=1;i<=n;i++){ if(dis[now][i]!=0&&!vis[i]){ if(sum+dis[now][i]>ans)continue; if(in&&step!=n-2)continue; sum+=dis[now][i]; vis[i]=1; dfs(i,step+1); vis[i]=0; sum-=dis[now][i]; } } } signed main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin>>n; vis[1]=1; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ cin>>dis[i][j]; } } dfs(1,0); cout<<ans; return 0; }
-
0
#include<bits/stdc++.h> using namespace std; #define int long long const int inf=2e7+10; int n,vis[20],dis[20][20],ans=inf,sum; void dfs(int now,int step){ int flag=0; if(stepn-1){ if(sum<ans){ ans=sum; } return; } for(int i=1;i<=n;i++){ if(dis[now][i]!=0&&!vis[i]){ if(sum+dis[now][i]>ans)continue; if(in&&step!=n-2)continue; sum+=dis[now][i]; vis[i]=1; dfs(i,step+1); vis[i]=0; sum-=dis[now][i]; } } } signed main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin>>n; vis[1]=1; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ cin>>dis[i][j]; } } dfs(1,0); cout<<ans; return 0; }
-
0
#include<bits/stdc++.h> using namespace std; #define int long long const int inf=2e7+10; int n,vis[20],dis[20][20],ans=inf,sum; void dfs(int now,int step){ int flag=0; if(stepn-1){ if(sum<ans){ ans=sum; } return; } for(int i=1;i<=n;i++){ if(dis[now][i]!=0&&!vis[i]){ if(sum+dis[now][i]>ans)continue; if(in&&step!=n-2)continue; sum+=dis[now][i]; vis[i]=1; dfs(i,step+1); vis[i]=0; sum-=dis[now][i]; } } } signed main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin>>n; vis[1]=1; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ cin>>dis[i][j]; } } dfs(1,0); cout<<ans; return 0; }
-
0
其实很简单 设置一个最小值，每次递归都更新这个最小值，要是时间超过这个最小值直接全部return
import java.util.List; import java.util.Scanner; public class 海贼王之伟大航路 { static List<Integer> list = new ArrayList<>();static int year=0;static int min = Integer.MAX_VALUE; static int []vis ;static int[][] step;static int[]dist;static int [][]island; static int time=0; public static void main(String[] args) { Scanner inputScanner = new Scanner(System.in); int num = inputScanner.nextInt(); island = new int[num+1][num+1]; vis = new int[num+1]; step = new int[num+1][num+1]; dist = new int[num + 1]; for (int i = 1; i <= num; i++) { for (int j = 1; j <= num ; j++) { island[i][j]=inputScanner.nextInt(); //i到j岛屿距离 } } vis[1]=1; //初始点已经走过 dfs(island,1,1); for(int i=0;i<list.size();i++) { if(list.get(i)<min) { min=list.get(i); } } System.out.println(min); } private static void dfs(int[][] island,int count,int index) { if(year>min) return; // TODO Auto-generated method stub if(count==island.length-1&&index==island.length-1) { min=Math.min(year,min); } for (int i = 1; i < island.length; i++) { if(island[index][i]!=0&&vis[i]!=1) { year+=island[index][i]; vis[i]=1; dfs(island,count+1,i); vis[i]=0; year-=island[index][i]; } } } } -
0
#include<bits/stdc++.h> using namespace std; // typedef long long ll; const int N=21; int n; int d[N][N]; bool st[N]; int ans=0x3f3f3f3f; void dfs(int u,int cnt,int cost) { if(cost>ans) return; if(cntn&&un) { ans=min(ans,cost); return; } for(int i=1;i<=n;i++) { if(i==u) continue; if(st[i]) continue; if(d[u][i]>ans) continue; st[i]=true; dfs(i,cnt+1,cost+d[u][i]); st[i]=false;; } } int main() { cin>>n; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { cin>>d[i][j]; } } st[1]=true; dfs(1,1,0); cout<<ans; return 0; }
-
0
使用dfs + 剪枝，最多可过70%数据
#include <bits/stdc++.h> using namespace std; const int N = 20; const int INF = 1e9; int mp[N][N]; int vis[N]; int n; int mn = INF; int mem[N][N][N]; int dfs(int x, int sum, int cnt) { if (cnt == n && x == n) { mn = min(mn, sum); return mn; } if (cnt == n || sum >= mn) { return INF; } for (int i = 1; i <= n; ++i) { if (!vis[i]) { vis[i] = 1; return dfs(i, sum + mp[x][i], cnt + 1); vis[i] = 0; } } } int main() { scanf("%d", &n); for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { scanf("%d", &mp[i][j]); } } vis[1] = 1; printf("%d\n", dfs(1,0,1)); return 0; }正解DP
#include <bits/stdc++.h> using namespace std; const int N = 20; const int INF = 1e9; int mp[N][N]; int dp[1 << N][N]; int n; int main() { scanf("%d", &n); for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { scanf("%d", &mp[i][j]); } } for (int i = 0; i < (1 << n); ++i) { for (int j = 0; j < n; ++j) { dp[i][j] = INF; } } dp[1][0] = 0; for (int i = 1; i < (1 << n); ++i) { for (int j = 0; j < n; ++j) { if ((i >> j) & 1) { for (int k = 0; k < n; ++k) { if ((i >> k) & 1 && j != k) { dp[i][j] = min(dp[i][j], dp[i ^ (1 << j)][k] + mp[k][j]); } } } } } printf("%d\n", dp[(1 << n) - 1][n - 1]); return 0; }
yuri01
LV 9
@ 2025-1-7 0:37:04
- 1
