k<=10，所以每用一次机会就跳到一个新图中，

每一个图按原图建边，相邻两图中建边权为0的边

补一补dj，好像我以前觉得dj特别难，hhhhh

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define N 500500using namespace std;int n,m,k,S,T;struct point{ int st,dis; bool operator < (const point &a)const{ return dis>a.dis; }}p[N];int e=1,head[N],dis[N];bool bo[N];struct edge{ int u,v,w,next;}ed[5000500];void add(int u,int v,int w){ ed[e].u=u; ed[e].v=v; ed[e].w=w; ed[e].next=head[u]; head[u]=e++;}priority_queue
          
            q;int dijkstra(){ memset(dis,0x7f,sizeof dis); memset(bo,0,sizeof bo); dis[S]=0;q.push((point){S,0}); while(!q.empty()){ point now=q.top();q.pop(); if(bo[now.st]) continue; bo[now.st]=1; for(int i=head[now.st];i;i=ed[i].next) if(dis[now.st]+ed[i].w