UVa 1424 - Salesmen
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN=1e4+5;
const int MAXM=1e5+5;
const int mod=1e9+7;
int n,m,dp[205][305],x[305],edge[205][200005],len;
int E[305][305];
/*void link(int a,int b){
len++; edge[len][0]=b;
if (edge[a][0]==0) edge[a][1]=len;
else edge[edge[a][0]][1]=len;
edge[a][0]=len;
}*/
int main(){
int aa; scanf("%d",&aa);
while(aa--){
scanf("%d%d",&n,&m);
//len=n; memset(edge,0,sizeof(edge));
memset(E,0,sizeof(E));
for(int i=1;i<=m;i++){
int a,b; scanf("%d%d",&a,&b);
E[a][b]=E[b][a]=1;
}
scanf("%d",&m);
for(int i=1;i<=m;i++) scanf("%d",&x[i]);
for(int i=1;i<=n;i++)
if (i==x[1]) dp[1][i]=0;
else dp[1][i]=1;
for(int i=1;i<m;i++){
for(int j=1;j<=n;j++) dp[i+1][j]=100000;
for(int j=1;j<=n;j++)
for(int k=1;k<=n;k++)
if (E[j][k]==1 || j==k) dp[i+1][k]=min(dp[i+1][k],dp[i][j]);
for(int j=1;j<=n;j++)
if (x[i+1]!=j) dp[i+1][j]++;
}
int ans=100000;
for(int i=1;i<=n;i++) ans=min(ans,dp[m][i]);
printf("%d\n",ans);
}
return 0;
}