题意：
一个无向图，从$1$到$n$，要求必须经过$2,3,...,k+1$，给出一些限制关系，要求在经过$v \le k+1$之前必须经过$u \le k+1$
求最短路
预处理出$1...k+1$到其他点的最短路
然后$f[i][s]$表示当前在$i$已经经过的点的集合为$s$的最短路
只考虑$1,2,...,k+1$就行了，
注意$1$也要考虑，一个点可能经过多次
然后实测dij比spfa快....我想试$pb\_ds$来着结果发现我的电脑上没有ext/pb_ds/priority_queue.hpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
const int N=2e4+,M=2e5+,K=,S=(<<)+,INF=1e9;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
int n,m,k,u,v,w;
int need[K],f[K][S];
int d[K][N];
struct Edge{
int v,w,ne;
}e[M<<];
int cnt,h[N];
inline void ins(int u,int v,int w){
cnt++;
e[cnt].v=v;e[cnt].w=w;e[cnt].ne=h[u];h[u]=cnt;
cnt++;
e[cnt].v=u;e[cnt].w=w;e[cnt].ne=h[v];h[v]=cnt;
}
int q[N],head,tail,inq[N];
inline void lop(int &x){if(x==N) x=;else if(x==) x=N-;}
void spfa(int s,int *d){
head=tail=;
d[s]=;inq[s]=;
q[tail++]=s;
while(head!=tail){
int u=q[head++];inq[u]=;lop(head);
for(int i=h[u];i;i=e[i].ne){
int v=e[i].v;
if(d[v]>d[u]+e[i].w){
d[v]=d[u]+e[i].w;
if(!inq[v]){
inq[v]=;
if(d[v]<d[q[head]]) head--,lop(head),q[head]=v;
else q[tail++]=v,lop(tail);
}
}
}
}
}
int main(){
freopen("in","r",stdin);
n=read();m=read();k=read();
for(int i=;i<=m;i++) u=read(),v=read(),w=read(),ins(u,v,w);
memset(d,,sizeof(d));
for(int i=;i<=k+;i++) spfa(i,d[i]);
int c=read();
while(c--) u=read()-,v=read(),need[v]|=(<<u); memset(f,-,sizeof(f));
int All=<<k;
f[][]=;
for(int s=;s<All;s++)
for(int i=;i<=k+;i++) if(f[i][s]!=-){
for(int j=;j<=k+;j++) if(j!=i && (need[j]&s)==need[j] ){
int t=s|(<<(j-));
if(f[j][t]>f[i][s]+d[i][j] || f[j][t]==-)
f[j][t]=f[i][s]+d[i][j];
}
}
int ans=INF;
for(int i=;i<=k+;i++)
if(f[i][All-]!=-) ans=min(ans,f[i][All-]+d[i][n]);
printf("%d",ans);
}
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
#define pii pair<int,int>
#define MP make_pair
#define fir first
#define sec second
typedef long long ll;
const int N=2e4+,M=2e5+,K=,S=(<<)+,INF=1e9;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
int n,m,k,u,v,w;
int need[K],f[K][S];
int d[K][N];
struct Edge{
int v,w,ne;
}e[M<<];
int cnt,h[N];
inline void ins(int u,int v,int w){
cnt++;
e[cnt].v=v;e[cnt].w=w;e[cnt].ne=h[u];h[u]=cnt;
cnt++;
e[cnt].v=u;e[cnt].w=w;e[cnt].ne=h[v];h[v]=cnt;
} priority_queue<pii,vector<pii>,greater<pii> > q;
bool done[N];
void dij(int s,int *d){
for(int i=;i<=n;i++) d[i]=INF,done[i]=;
d[s]=;
q.push(MP(d[s],s));
while(!q.empty()){
int u=q.top().sec;q.pop();
if(done[u]) continue;done[u]=;
for(int i=h[u];i;i=e[i].ne)
if(d[e[i].v]>d[u]+e[i].w){
d[e[i].v]=d[u]+e[i].w;
q.push(MP(d[e[i].v],e[i].v));
}
}
}
int main(){
freopen("in","r",stdin);
n=read();m=read();k=read();
for(int i=;i<=m;i++) u=read(),v=read(),w=read(),ins(u,v,w);
memset(d,,sizeof(d));
for(int i=;i<=k+;i++) dij(i,d[i]);
int c=read();
while(c--) u=read()-,v=read(),need[v]|=(<<u); memset(f,-,sizeof(f));
int All=<<k;
f[][]=;
for(int s=;s<All;s++)
for(int i=;i<=k+;i++) if(f[i][s]!=-){
for(int j=;j<=k+;j++) if(j!=i && (need[j]&s)==need[j] ){
int t=s|(<<(j-));
if(f[j][t]>f[i][s]+d[i][j] || f[j][t]==-)
f[j][t]=f[i][s]+d[i][j];
}
}
int ans=INF;
for(int i=;i<=k+;i++)
if(f[i][All-]!=-) ans=min(ans,f[i][All-]+d[i][n]);
printf("%d",ans);
}