Long time ago, there were n cities in a country named ABP(A Beautiful Place).
There was an interconnected network of trade routes among some of the cities. Realized that a powerful nation was based on good connection among the cities, the King of the country make a decision to set up a freeway network, which is also known as the Silk Road Project. The king selected k wealthy cities to take the lead in setting up the freeway network. Here are the Silk Road Project’s rules: 1. In order to save costs, the freeway must be built at the basis on the original routes. 2. Every two selected cities can connect to each other by the freeway. 3. There will be no more than 10 unselected cities. Notice that there is NO city has the trade route connect to itself, and no more than ONE direct trade route between two cities.

输入格式
The input consists of T test cases. T is given in the first line of the input file.
Each test case begins with the first line containing three integer, n, m, k. n for n cities(2 <= n <= 100), m for m trade routes, k for k selected cities.
The second line for each case contains k positive integers representing the selected cities, numbered from 1 to n.
The following m lines contain triples of integers ai, bi, vi(1<=vi<=10000) . Where vi for the cost of building a freeway between ai and bi city.
There is an empty line after each test case.


输出格式
For each testcase, outputs should be set in one line.
If the Silk Road Project can be worked out, a positive integer should be printed to show the minimum cost.
Otherwise, the output should be “No solution!”.


输入样例
2

3 2 2
1 2
1 2 3
2 3 4

3 2 2
1 3
1 2 3
2 3 4


输出样例
3
7

这是我的代码


#include <cstdio>
#include <cstdlib>
#include <sstream>
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <string>
#include <utility>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <deque>
using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
#define PB push_back
#define ft first
#define sd second
#define lowbit(x) (x&(-x))
#define INF (1<<30)
#define eps (1e-8)
typedef     struct{
    int b;
    int cost;
}node;
vector < node > G[105];
int sele[105];
int vis[105];
int n,m,k;
long long ans;
int cnt;
void dfs(int i,int sum)
{
    vis[i]=1;
    if(k==0)
    {
        ans=min(ans,(long long)sum);
        return ;
    }
    int len=G[i].size();
    for(int j=0;j<len;j++)
    {
        if(!vis[G[i][j].b])
        {
            //printf("%d->%d\n",i,G[i][j].b);
            if(sele[G[i][j].b])    k--;
            dfs(G[i][j].b,sum+G[i][j].cost);
            if(sele[G[i][j].b]) k++;
            vis[G[i][j].b]=0;
        }   
    }
}
void solve()
{
    for(int i=0;i<105;i++)
        G[i].clear();
    scanf("%d%d%d",&n,&m,&k);
    int tmp;
    memset(sele,0,sizeof(sele));
    memset(vis,0,sizeof (vis));
    for(int i=0;i<k;i++)
    {   
        scanf("%d",&tmp);
        sele[tmp]=1;
    }
    int u,v,ca;
    node tmp1,tmp2;
    while(m--)
    {
        scanf("%d%d%d",&u,&v,&ca);
        tmp1.b=u,tmp1.cost=ca;   
        tmp2.b=v,tmp2.cost=ca;
        if(sele[u]||sele[v])
        {
            G[v].push_back(tmp1);
            G[u].push_back(tmp2);
        }
    }
    ans=INF;
    k--;
    dfs(tmp,0);
    if(ans==INF) printf("No solution!\n");
    else printf("%lld\n",ans);
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
        solve();
    return 0;   
}

只求教下怎么优化

时限是1200ms