提交记录 27326
提交时间 |
评测时间 |
2024-11-09 21:03:23 |
2024-11-09 21:03:28 |
#include<bits/stdc++.h>
using namespace std;
const int inf=2e9;
int n,m;
int c[20][20],to[20][20],num[20];
int p,ans=inf;
int tmp=0;
int tot,cnt,vis[20],di[20];
inline bool cmp(int a,int b)
{
return c[p][a]<c[p][b];
}
inline void dfs(int st,int sti)
{
for(int i=st;i<=cnt;i++)
{
int si=vis[i];
if(tot+tmp*di[si]>=ans)
{
return;
}
for(int j=sti;j<=num[si];j++)
{
int sj=to[si][j];
if(!di[sj])
{
cnt++;
vis[cnt]=sj;
tmp-=c[sj][to[sj][1]];
tot+=di[si]*c[si][sj];
di[sj]=di[si]+1;
dfs(i,j+1);
tot-=di[si]*c[si][sj];
di[sj]=0;
tmp+=c[sj][to[sj][1]];
cnt--;
}
}
sti=1;
}
if(cnt==n)
{
ans=min(ans,tot);
return;
}
}
int main()
{
cin>>n>>m;
for(int i=0;i<20;i++)
{
for(int j=0;j<20;j++)
{
c[i][j]=inf;
}
}
for(int i=1;i<=m;i++)
{
int u,v,w;
cin>>u>>v>>w;
if(c[u][v]<w) continue;
if(c[u][v]==inf)
{
to[u][++num[u]]=v,to[v][++num[v]]=u;
}
c[u][v]=c[v][u]=w;
}
for(int i=1;i<=n;i++)
{
p=i;
sort(to[i]+1,to[i]+num[i]+1,cmp);
tmp+=c[i][to[i][1]];
}
//cout<<tmp;
for(int i=1;i<=n;i++)
{
tot=0,cnt=1;
vis[1]=i;
tmp-=c[i][to[i][1]];
di[i]=1;
dfs(1,1);
di[i]=0;
tmp+=c[i][to[i][1]];
}
cout<<ans;
return 0;
}
Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
Testcase #1 | 43.61 us | 40 KB | Accepted | Score: 5 | 显示更多 |
Testcase #2 | 40.71 us | 40 KB | Accepted | Score: 5 | 显示更多 |
Testcase #3 | 41.65 us | 40 KB | Accepted | Score: 5 | 显示更多 |
Testcase #4 | 40.62 us | 40 KB | Accepted | Score: 5 | 显示更多 |
Testcase #5 | 43.89 us | 40 KB | Accepted | Score: 5 | 显示更多 |
Testcase #6 | 57.06 us | 40 KB | Accepted | Score: 5 | 显示更多 |
Testcase #7 | 43.67 us | 40 KB | Accepted | Score: 5 | 显示更多 |
Testcase #8 | 48.87 us | 40 KB | Accepted | Score: 5 | 显示更多 |
Testcase #9 | 239.92 us | 40 KB | Accepted | Score: 5 | 显示更多 |
Testcase #10 | 132.45 us | 40 KB | Accepted | Score: 5 | 显示更多 |
Testcase #11 | 99.79 us | 40 KB | Accepted | Score: 5 | 显示更多 |
Testcase #12 | 105.69 us | 40 KB | Accepted | Score: 5 | 显示更多 |
Testcase #13 | 111.77 us | 40 KB | Accepted | Score: 5 | 显示更多 |
Testcase #14 | 146.3 us | 40 KB | Accepted | Score: 5 | 显示更多 |
Testcase #15 | 478.31 us | 40 KB | Accepted | Score: 5 | 显示更多 |
Testcase #16 | 605.68 us | 40 KB | Accepted | Score: 5 | 显示更多 |
Testcase #17 | 432.05 us | 40 KB | Accepted | Score: 5 | 显示更多 |
Testcase #18 | 470.19 us | 40 KB | Accepted | Score: 5 | 显示更多 |
Testcase #19 | 1.196 ms | 40 KB | Accepted | Score: 5 | 显示更多 |
Testcase #20 | 818.61 us | 40 KB | Accepted | Score: 5 | 显示更多 |
Judge Duck Online | 评测鸭在线
Server Time: 2024-12-04 10:36:44 | Loaded in 1 ms | Server Status
个人娱乐项目,仅供学习交流使用 | 捐赠