这题有两问，第一问用状压DP的思想解决，第二问用统计最短路条数的方法解决。毕竟dp是一种特殊的最短路问题嘛，具体看注释吧，写得还算详细

#include<bits/stdc++.h>
using namespace std;

const int N=15,M=1<<13;

int f[N][N][M]; //f[i][j][a]为走过的点的状态为a,现在停留在j，并且上次停留在i的所有方案的最大价值
int num[N][N][M]; //num[i][j][a]为走过的点的状态为a,现在停留在j，并且上次停留在i的所有方案中能达到最大价值的方案数目
int n,m,T,val[N]; //val[i]为的点权
bool g[N][N]; //g[i][j]为ture说明i到j有边
int tmp[N][N][N]; //tmp[i][j][k]为当前在j点，上次在i点，然后现在走到了k点，所增加的价值

int main()
{
    cin>>T;
    while(T--)
    {
        //清空数据，读入数据
        memset(num,0,sizeof num);
        memset(f,-0x3f,sizeof f);
        memset(g,0,sizeof g);
        memset(tmp,0,sizeof tmp);
        cin>>n>>m;
        for(int i=0;i<n;i++) cin>>val[i];
        while(m--)
        {
            int x,y;cin>>x>>y;
            x--,y--;
            g[x][y]=g[y][x]=true;
        }

        //初始化两个dp数组,因为初始状态只有当前的起点没有上一点，我这里人为设定把上一点等同于当前点了
        for(int i=0;i<n;i++)
            f[i][i][1<<i]=val[i],num[i][i][1<<i]=1;

        //预处理tmp，加速运算，不过不预处理应该也能过
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                for(int k=0;k<n;k++)
                {
                    int sum=val[k]+val[k]*val[j];
                    if(g[i][j]&&g[j][k]&&g[k][i]) sum+=val[i]*val[k]*val[j]; //若i,j,k三者能成环，则加上
                    tmp[i][j][k]=sum;
                }

        //DP过程，转移的方式是“我为人人”
        for(int a=0;a<(1<<n)-1;a++)
            for(int i=0;i<n;i++)
                for(int j=0;j<n;j++)
                {
                    int v=f[i][j][a],cnt=num[i][j][a];

                    if(v<-100000000) continue; //非法状态，不必转移
                    for(int k=0;k<n;k++)
                    {
                        if(a>>k&1||!g[j][k]) continue; //如果已经走过了k或者j和k没有边，则continue

                        if(f[j][k][a|(1<<k)]<tmp[i][j][k]+v) //有更好的，则更新
                        {
                            f[j][k][a|(1<<k)]=tmp[i][j][k]+v;
                            num[j][k][a|(1<<k)]=cnt;
                        }else if(f[j][k][a|(1<<k)]==tmp[i][j][k]+v) //和之前的价值相等，则更新方案数目
                        {
                            num[j][k][a|(1<<k)]+=cnt;
                        }
                    }
                }

        //处理输出，别忘了sum得除2
        int ans=-0x3f3f3f3f,sum=0;
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                {
                    if(ans<f[i][j][(1<<n)-1])
                    {
                        ans=f[i][j][(1<<n)-1];
                        sum=num[i][j][(1<<n)-1];
                    }else if(ans==f[i][j][(1<<n)-1]) sum+=num[i][j][(1<<n)-1];
                }
        if(ans<0) puts("0 0");
        else cout<<ans<<' '<<sum/2<<endl;
    }
    return 0;
}