这题事实上只需要关心15个商店和一个起点一个终点，预处理出这几个点之间的最短距离。Floyd会超时，用Dijkstra即可。
然后就是dp[u][S]表示已经经过商店集合S且当前在第u个商店所花的最少时间。
最后的结果是找到所有dp[u][S]有解且u能到达终点的最大的|S|，而最短时间就是dp[u][S]+dist[u][vt]。
细节还挺多的。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define INF (1<<29) int d[][<<];
int G[][],dist[][],shop[];
void dijkstra(int vs,int n){
for(int i=; i<n; ++i) dist[vs][i]=INF;
dist[vs][vs]=;
bool vis[]={};
for(int i=; i<n; ++i){
int u=-,mm=INF;
for(int v=; v<n; ++v){
if(!vis[v] && mm>dist[vs][v]){
mm=dist[vs][v];
u=v;
}
}
if(u==-) break;
vis[u]=;
for(int v=; v<n; ++v){
if(!vis[v] && G[u][v]!=INF && dist[vs][v]>dist[vs][u]+G[u][v]){
dist[vs][v]=dist[vs][u]+G[u][v];
}
}
}
}
int getCnt(int s){
int res=;
for(int i=; i<; ++i){
if((s>>i)&) ++res;
}
return res;
}
int cnt[<<];
int main(){
for(int i=; i<(<<); ++i) cnt[i]=getCnt(i);
int t,n,m,s,a,b,c;
scanf("%d",&t);
for(int cse=; cse<=t; ++cse){
scanf("%d%d%d",&n,&m,&s);
for(int i=; i<n; ++i){
for(int j=; j<n; ++j) G[i][j]=INF;
}
for(int i=; i<s; ++i) scanf("%d",&shop[i]);
while(m--){
scanf("%d%d%d",&a,&b,&c);
G[a][b]=min(G[a][b],c);
}
dijkstra(,n);
for(int i=; i<s; ++i) dijkstra(shop[i],n); if(dist[][n-]==INF){
printf("Case %d: Impossible\n",cse);
continue;
} for(int i=; i<s; ++i){
for(int j=; j<(<<s); ++j) d[i][j]=INF;
}
for(int i=; i<s; ++i){
d[i][<<i]=dist[][shop[i]];
}
for(int i=; i<(<<s); ++i){
for(int j=; j<s; ++j){
if(((i>>j)&)==) continue;
for(int k=; k<s; ++k){
if(k==j || ((i>>k)&)==) continue;
d[j][i]=min(d[j][i],d[k][i^(<<j)]+dist[shop[k]][shop[j]]);
}
}
}
int mx=,mm=INF;
for(int i=; i<(<<s); ++i){
for(int j=; j<s; ++j){
if(d[j][i]==INF || dist[shop[j]][n-]==INF) continue;
mx=max(mx,cnt[i]);
}
}
for(int i=; i<(<<s); ++i){
for(int j=; j<s; ++j){
if(d[j][i]==INF) continue;
if(cnt[i]==mx) mm=min(mm,d[j][i]+dist[shop[j]][n-]);
}
}
if(mm!=INF) printf("Case %d: %d %d\n",cse,mx,mm);
else printf("Case %d: 0 %d\n",cse,dist[][n-]);
}
return ;
}