公元215年，刘备取益州，孙权令诸葛瑾找刘备索要荆州。刘备不答应，孙权极为恼恨，便派吕蒙率军取长沙、零陵、桂阳三郡。长沙、桂阳蜀将当即投降。刘备得知后，亲自从成都赶到公安(今湖北公安)，派大将关羽争夺三郡。孙权也随即进驻陆口，派鲁肃屯兵益阳，抵挡关羽。双方剑拔弩张，孙刘联盟面临破裂，在这紧要关头，鲁肃为了维护孙刘联盟，不给曹操可乘之机，决定当面和关羽商谈。“肃邀羽相见，各驻兵马百步上，但诸将军单刀俱会”。双方经过会谈，缓和了紧张局势。随后，孙权与刘备商定平分荆州，“割湘水为界，于是罢军”，孙刘联盟因此能继续维持。
【问题描述】
关羽受鲁肃邀请，为了大局，他决定冒险赴会。他带着侍从周仓，义子关平，骑着赤兔马，手持青龙偃月刀，从军营出发了，这就是历史上赫赫有名的“单刀赴会”。关羽平时因为军务繁重，决定在这次出行中拜访几个多日不见的好朋友。然而局势紧张，这次出行要在限定时间内完成，关公希望你能够帮助他安排一下行程，安排一种出行方式，使得从军营出发，到达鲁肃处赴会再回来，同时拜访到尽可能多的朋友，在满足这些条件下行程最短。注意拜访朋友可以在赴会之前，也可以在赴会之后。现在给出地图，请你完成接下来的任务。
我们发现k非常的小，这种问题是经典的状压DP，又因为是无环图，所以可以用dijk先算出每个关键点到其他点的距离，再调用TSP问题的方法即可
（这里说一下：dijk+heap很好写，信不信比你的spfa还短，而且可以在负权图上面跑！但是效率会下降很多）
#pragma GCC opitmize("O3")
#pragma G++ opitmize("O3")
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
using namespace std;
struct Node{ int d,id; } x;
struct Edge{ int v,c,nt; } G[100010];
int h[10010],d[20][10010],d2[20][20];
int n,m,k,t,cnt=0,w[20],f[20][1<<18];
inline bool gmin(int& a,int b){ return a>b?(a=b)|1:0; }
inline bool operator < (Node a,Node b){ return a.d>b.d; }
inline int tot(int s,int c=0){ for(;s;s^=s&-s) ++c; return c; }
inline void adj(int x,int y,int c){ G[++cnt]=(Edge){y,c,h[x]}; h[x]=cnt; }
void dijk(int* d,int s){
priority_queue<Node> q;
d[s]=0; q.push((Node){0,s});
for(int u;!q.empty();){
x=q.top(); q.pop();
if(d[u=x.id]<x.d) continue;
for(int v,i=h[u];i;i=G[i].nt)
if(gmin(d[v=G[i].v],d[u]+G[i].c)) q.push((Node){d[v],v});
}
}
int main(){
scanf("%d%d%d%d",&n,&m,&k,&t);
for(int x,y,c;m--;){
scanf("%d%d%d",&x,&y,&c);
adj(x,y,c); adj(y,x,c);
}
memset(d,63,sizeof d);
memset(f,63,sizeof f);
w[0]=1; w[++k]=n;
dijk(d[0],1); dijk(d[k],n);
for(int i=1;i<k;++i){
scanf("%d",w+i);
dijk(d[i],w[i]);
for(int j=0;j<i;++j) d2[i][j]=d2[j][i]=d[i][w[j]];
}
for(int j=0;j<k;++j){
d2[k][j]=d2[j][k]=d[k][w[j]];
f[j][1<<j]=d2[0][j];
}
for(int S=0;S<(1<<k+1);++S)
for(int i=0;i<=k;++i)
if(S&(1<<i))
for(int j=0;j<=k;++j)
if(i!=j&&(S&(1<<j)))
f[i][S]=min(f[i][S],f[j][S-(1<<i)]+d2[j][i]);
int Mx=-1,Ml=0;
for(int S=1<<k;S<(1<<k+1);++S)
if((S&(1<<k))&&(S&1)){
int c=tot(S)-2,v=1<<30;
if(c>=Mx){
for(int j=0;j<=k;++j)
v=min(v,f[j][S]+d2[0][j]);
if(v<=t){
if(Mx==c) gmin(Ml,v);
else Ml=v; Mx=c;
}
}
}
if(~Mx) printf("%d %d",Mx,Ml); else puts("-1");
}