本文主要是介绍HDU 3768 Shopping spfa+dfs枚举，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：从一个点出发经过指定的点，然后回到起点，找最短路。
想法：先求出起点以及每一个要经过的商店点的单源最短路，即求S+1次spfa，因为只有最多10个商店，可以枚举商店访问的先后顺序，然后取出最小值即可。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#define inf 0x7fffffff
using namespace std;
const int nodes=100000+50;
const int edges=200000+50;
int n,m,s;
int ss[15],dis[11][nodes],res;
struct node
{int v,next,w;
}e[edges];
int head[nodes],cnt,vis[15],used[15];
void Init()
{memset(head,-1,sizeof(head));cnt=0;
}
void add(int a,int b,int c)
{e[cnt].v=b;e[cnt].next=head[a];e[cnt].w=c;head[a]=cnt++;
}
void spfa(int st,int *dis)
{int vis[nodes];queue<int>q;while(!q.empty()) q.pop();for(int i=0;i<n;i++){dis[i]=inf;vis[i]=0;}dis[st]=0;vis[st]=1;q.push(st);while(!q.empty()){int u=q.front();q.pop();vis[u]=0;for(int i=head[u];i+1;i=e[i].next){int v=e[i].v;if(dis[v]>dis[u]+e[i].w){dis[v]=dis[u]+e[i].w;if(!vis[v]){vis[v]=1;q.push(v);}}} }
}
void dfs(int passnum)
{if(passnum>s) return;if(passnum==s){int sum=dis[0][ss[vis[1]]];for(int i=1;i<s;i++){sum+=dis[vis[i]][ss[vis[i+1]]];}sum+=dis[vis[s]][0];if(sum<res)res=sum;return;}for(int i=1;i<=s;i++){if(!used[i]){used[i]=1;vis[passnum+1]=i;dfs(passnum+1);used[i]=0;}}return;
}
int main()
{int test;scanf("%d",&test);while(test--){scanf("%d%d",&n,&m);Init();for(int i=1;i<=m;i++){int a,b,c;scanf("%d%d%d",&a,&b,&c);add(a,b,c);add(b,a,c);}scanf("%d",&s);spfa(0,dis[0]);for(int i=1;i<=s;i++){scanf("%d",&ss[i]);spfa(ss[i],dis[i]);}memset(used,0,sizeof(used));res=inf;dfs(0);printf("%d\n",res);}return 0;
}这篇关于HDU 3768 Shopping spfa+dfs枚举的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
