本题中文题意略有不清， 再看了英文之后我才知道， 你需要在 $2-k+1$ 这几个城市停留， 在这之前可以随意经过， 限制条件是对于停留而言的。

到这里， 就容易想到状压。 令 $f(s,i)$ 表示现在已经在 $s$ 集合中的城市停留， 现在在第 $i$ 个城市的最短路径长度。 令 $u_i$ 表示第 $i$ 个城市的前置集合。 那么 $f(s,i)$ 成立的条件是 $u_i\subset s$， 有转移方程：

$$f(s,i)=\min_{j\in s-\{i\}}\{f(s-\{i\},j)+dis_{j,i} \}$$

其中边界条件为 $f(\{i\},i)=dis_{1,i}, ~u_i=\varnothing$。

容易想到先用堆优 $\texttt{dijkstra}$ 跑 $k$ 个点的最短路， 算出两两之间的 $dis$， 就可以开始转移了。

容易发现这样要爆空间， 容易想到滚动数组。 观察转移方程， 发现转移集合 $s$ 需要用到的集合大小只比 $s$ 小 $1$， 那么可以先处理每个集合的元素个数， 把集合大小作为拓扑序， 就可以使用滚动数组了。

时间复杂度： $\Theta(km\log m+2^kk^2)$。

Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=2e4+5,M=2e5+5;
int read(){
	int ans=0;char c=getchar();
	while(c<'0'||c>'9') c=getchar();
	while('0'<=c&&c<='9') ans=(ans<<1)+(ans<<3)+c-'0',c=getchar();
	return ans;
}
struct node{
	int v,w;
	bool operator<(const node &b)const{
		return w>b.w;
	}
};
int n,m,k,Q,uset[21];
int tl[21][21],Map[21],kdis[21][2],sum[(1<<20)+1];
int f[2][184757][21],cur,pMap[(1<<20)+1];
vector <int> p[21];
vector <node> s[N];
priority_queue <node> q;
int dis[N];
bool vis[N];
void dijkstra(int S){
	memset(dis,0x3f,sizeof dis);dis[Map[S]]=0;memset(vis,0,sizeof vis);
	q.push({Map[S],0});
	while(!q.empty()){
		node x=q.top();q.pop();
		if(vis[x.v]) continue;
		vis[x.v]=1;
		int len=s[x.v].size();
		for(int i=0; i<len; i++){
			node t=s[x.v][i];
			if(!vis[t.v]&&dis[t.v]>dis[x.v]+t.w){
				dis[t.v]=dis[x.v]+t.w;
				q.push({t.v,dis[t.v]});
			}
		}
	}
	kdis[S][0]=dis[1],kdis[S][1]=dis[n];
	for(int i=0; i<k; i++) tl[S][i]=dis[Map[i]];
}

int main(){
	n=read();m=read();k=read();
	for(int i=1; i<=m; i++){
	    int u=read(),v=read(),w=read();
	    s[u].push_back({v,w});s[v].push_back({u,w});
	}
	if(k==0){
		Map[1]=1;
		dijkstra(1);
		printf("%d\n",dis[n]);
		return 0;
	}
	for(int i=0; i<k; i++){
		Map[i]=i+2;
	}
	for(int s=1; s<(1<<k); s++) sum[s]=sum[s&(~(s&-s))]+1,p[sum[s]].push_back(s),pMap[s]=p[sum[s]].size()-1;
	Q=read();
	while(Q--){
		int u=read(),v=read();
		uset[v-2]|=(1<<(u-2));
	}
	memset(f,0x3f,sizeof f);
	for(int i=0; i<k; i++){
		dijkstra(i);if(!uset[i]) f[0][pMap[1<<i]][i]=kdis[i][0];
	} 
	for(int w=2; w<=k; w++){
		int len=p[w].size();cur^=1;memset(f[cur],0x3f,sizeof f[cur]);
		for(int e=0; e<len; e++){
			int s=p[w][e];
			for(int i=0; i<k; i++) if((s&(1<<i))&&((uset[i]&(s&(~(1<<i))))==uset[i])){
				for(int j=0; j<k; j++) if(i!=j&&(s&(1<<j))){
					f[cur][e][i]=min(f[cur][e][i],f[cur^1][pMap[s&(~(1<<i))]][j]+tl[j][i]);
				}
			}
		}
	}
	int ans=0x3f3f3f3f;
	for(int i=0; i<k; i++) ans=min(ans,f[cur][0][i]+kdis[i][1]);
	printf("%d\n",ans);
	return 0;
}