最短路深搜

佚名 6年前 (2019-04-12) 随笔 1743人围观抢沙发百度已收录

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

↑杭电oj ----2544

#include <cstdio>
#include <cstring>using namespace std;
const int INF=0x3f3f3f3f;
int n,m,a,b,c,mp[105][105],ans;
bool use[105];
void dfs(int k,int l){
for(int i=2;i<=n;i++)
{
   if(l>ans) return;
   if(k==n)
{
   ans=l;
   return;
}
if(use[i]==false)
{
   use[i]=true;
   dfs(i,l+mp[k][i]);
   use[i]=false;
}
}
}
int main()
{
   while(scanf("%d%d",&n,&m)!=EOF&&(n||m))
   {
   ans=INF;
   memset(mp,INF,sizeof(mp));
   for(int i=1;i<=m;i++)
   {
   scanf("%d%d%d",&a,&b,&c);
   if(mp[a][b]>c)
   mp[a][b]=mp[b][a]=c;
   }
   use[1]=true;
   dfs(1,0);
   printf("%d\n",ans);
   }
   return 0;
}