这道题算经典的状压DP了。。

DP[S][P]表示完成了S集合的任务，现在在第P个任务的落脚点。。。

那么直接推就OK了。。

#include<iostream>
#include<string.h>
#include<queue>
#define REP(i,n) for(int i=0;i<n;i++)
#define Renew(x,c) x=min(x,c)
#define floyd(d) REP(k,n) REP(i,n) REP(j,n) Renew(d[i][j],d[i][k]+d[k][j]);
using namespace std;
const int maxn=120,inf=~0U>>3,maxb=13;
int n,m,b,cnt=0;
int dist[maxn][maxn];
int Go[maxb+1],Reach[maxb+1];

void init(){
    cin>>n>>m>>b;b--;cnt=0;
    REP(i,n) REP(j,n) dist[i][j]=(i==j?0:inf);
    while(m--) {
        int s,t,c;cin>>s>>t>>c;s--;t--;
        dist[s][t]=dist[t][s]=min(c,dist[s][t]);
    }
    int z;cin>>z; while(z--) {
        int s,t,c;cin>>s>>t>>c;s--;t--; while(c--) {
            Go[cnt]=s;Reach[cnt]=t;cnt++;
        }
    }
    Reach[cnt]=b;
}

int dp[1<<maxb][maxb+1];

struct node{
    int f,p;
    node(int f,int p):f(f),p(p){}
};

void solve(){
    floyd(dist); memset(dp,0,sizeof(dp));
    queue<node> Q; Q.push(node(0,cnt)); while(Q.size()){
        node cur=Q.front();Q.pop();
        int cost=dp[cur.f][cur.p];
        for(int i=0;i<cnt;i++)if(!(cur.f&(1<<i))) {
            int nf=cur.f|(1<<i); int get=cost+dist[Reach[cur.p]][Go[i]]+dist[Go[i]][Reach[i]];
            if(dp[nf][i]==0||dp[nf][i]>get) dp[nf][i]=get,Q.push(node(nf,i));
        }
    }
    int ans=inf; REP(i,cnt) Renew(ans,dp[(1<<cnt)-1][i]+dist[Reach[i]][b]); cout<<ans<<endl;
}5

int main(){
    int t;cin>>t; while(t--) {
        init(); solve();
    }
}