Shopping（hdu 3768）

题意：给你一个无向图，求从0号点开始遍历所有的指定点再回到0号点的最短路径

#include<cstdio>

#include<iostream>

#include<queue>

#include<algorithm>

#include<cstring>

#define N 100010

#define ll long long

#define INF 10000000000000LL

using namespace std;

ll head[N],vis[N],dis[N],f[][],a[],b[],n,m,k,ans=INF;

struct node

{

    ll v,pre,t;

};node e[N*];

ll read()

{

    ll num=,flag=;char c=getchar();

    while(c<''||c>''){if(c=='-')flag=-;c=getchar();}

    while(c>=''&&c<=''){num=num*+c-'';c=getchar();}

    return num*flag;

}

void add(ll i,ll x,ll y,ll z)

{

    e[i].v=y;

    e[i].t=z;

    e[i].pre=head[x];

    head[x]=i;

}

ll spfa(ll s,ll t)

{

    for(ll i=;i<=n;i++)dis[i]=INF;

    memset(vis,,sizeof(vis));

    queue<int> q;

    q.push(s);vis[s]=;dis[s]=;

    while(!q.empty())

    {

        ll u=q.front();vis[u]=;q.pop();

        for(ll i=head[u];i;i=e[i].pre)

          if(dis[e[i].v]>dis[u]+e[i].t)

          {

              dis[e[i].v]=dis[u]+e[i].t;

              if(!vis[e[i].v])

              {

                  vis[e[i].v]=;

                  q.push(e[i].v);

              }

          }

    }

    return dis[t];

}

void work()

{

    n=read();m=read();

    for(ll i=;i<=m;i++)

    {

        ll x=read()+,y=read()+,z=read();

        add(i*-,x,y,z);add(i*,y,x,z);

    }

    k=read();a[]=;

    for(ll i=;i<=k+;i++)

      a[i]=read()+;

    for(ll i=;i<=k+;i++)

      for(ll j=i+;j<=k+;j++)

        f[i][j]=f[j][i]=spfa(a[i],a[j]);

    for(ll i=;i<=k+;i++)b[i]=i;

    do

    {

        ll p=f[b[]][b[k+]];

        for(ll i=;i<=k+;i++)

          p+=f[b[i-]][b[i]];

        ans=min(ans,p);

    }while(next_permutation(b+,b+k+));

    cout<<ans<<endl;

}

int main()

{

    freopen("jh.in","r",stdin);

    ll T=read();

    while(T--)

    {

        memset(head,,sizeof(head));

        memset(f,,sizeof(f));

        memset(a,,sizeof(a));

        memset(b,,sizeof(b));

        memset(e,,sizeof(e));

        ans=INF;

        work();

    }

    return ;

}