卡时间卡的恶心
#pragma GCC optimize(3,"Ofast","inline")
#include<iostream>
#include <cstring>
using namespace std;
int n,m;
int g[11][11];
int st[11];
int sum;
int k;
void dfs(int x,int y)
{
if(k>=sum) return ;
if(y==n){
sum=k;
return;
}
for(int i=1;i<=n;i++){
if(g[x][i]!=0x3f3f3f3f&&st[i]<2){
st[i]++;
k+=g[x][i];
if(st[i]==1) dfs(i,y+1);
else dfs(i,y);
k-=g[x][i];
st[i]--;
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
while(cin>>n>>m){
memset(g,0x3f,sizeof g);
sum=1e5;
for(int i=0;i<m;i++){
int a,b,c;
cin>>a>>b>>c;
g[a][b]=c;
g[b][a]=c;
}
for(int i=1;i<=n;i++){
memset(st,0,sizeof st);
k=0;
st[i]=1;
dfs(i,1);
}
if(sum!=1e5) cout<<sum<<endl;
else cout<<-1<<endl;
}
return 0;
}
算法1
(暴力枚举) O(n2)
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) O(n2)
blablabla
时间复杂度
参考文献
C++ 代码
blablabla