事实上这份代码在洛谷过不去，因为好像要用到一些压缩空间的技巧，我并不想(hui)写(捂脸)
先预处理$1$到$k+1$这些点之间相互的最短路和它们到终点的最短路，并记录下每个点能够转移到时的状态，然后就是状压dp辣。
设$dp[s][i]$表示状态为$s$时处在点$i$的最短路，就可以$O(2^kk^2)$转移了，注意最好减一些不合法状态，因为这时间挺危险的=。=
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=,M=,K=,inf=0x3f3f3f3f;
struct a{int node,dist;};
bool operator < (a x,a y)
{
return x.dist>y.dist;
}
priority_queue<a> hp;
int dis[N],vis[N],ss[K],dp[(<<)+][K];
int p[N],noww[*M],goal[*M],val[*M],mat[K][K];
int n,m,k,c,t1,t2,t3,cnt,len,all,ans=inf;
void link(int f,int t,int v)
{
noww[++cnt]=p[f],p[f]=cnt;
goal[cnt]=t,val[cnt]=v;
}
void Dijkstra(int s)
{
memset(vis,,sizeof vis);
memset(dis,0x3f,sizeof dis);
dis[s]=,hp.push((a){s,});
while(!hp.empty())
{
a tt=hp.top(); hp.pop(); int tn=tt.node;
if(vis[tn]) continue ; vis[tn]=true;
for(int i=p[tn];i;i=noww[i])
if(dis[goal[i]]>dis[tn]+val[i])
dis[goal[i]]=dis[tn]+val[i],hp.push((a){goal[i],dis[goal[i]]});
}
}
int ins(int x)
{
return <<(x-);
}
int main ()
{
scanf("%d%d%d",&n,&m,&k),all=(<<k)-;
for(int i=;i<=m;i++)
{
scanf("%d%d%d",&t1,&t2,&t3);
link(t1,t2,t3),link(t2,t1,t3);
}
scanf("%d",&c);
for(int i=;i<=c;i++)
scanf("%d%d",&t1,&t2),ss[t2]|=ins(t1);
for(int i=;i<=k+;i++)
{
Dijkstra(i);
for(int j=;j<=k+;j++)
mat[i][j]=dis[j]; mat[i][]=dis[n];
}
memset(dp,0x3f,sizeof dp),dp[][]=;
for(int i=;i<=all;i++)
for(int j=;j<=k+;j++)
if(dp[i][j]!=inf)
for(int h=;h<=k+;h++)
if((i&ss[h])==ss[h])
dp[i|ins(h)][h]=min(dp[i|ins(h)][h],dp[i][j]+mat[j][h]);
for(int i=;i<=k+;i++) ans=min(ans,dp[all][i]+mat[i][]);
printf("%d",ans);
return ;
}