Aimeeeeeeeeeeeeeeeeeeee

人是会变的
我从没想过有一天我会不想放假

一个小小的A*，求出来每一个点到终点的距离作为估价函数

（显然这是最乐观的情况）

然后就是一个搜索了

搜索的key就是估价+走过的距离

并且显然如果一个点已经被取出了k次，那么这个点就是不会对第k条路起作用了

那么就扔掉

Aimee Aimee Aimee

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue> 
using namespace std;
int n,m;
int head[1005][2];
struct b{
    int to;
    int ne;
    int v;
} e[200001][2];
int Aimee[1005];
int x,y,z;
struct nod{
    int po;
    int dis;
    int di;
    friend bool operator < ( nod x, nod y) {
        return x.dis>y.dis;
    } 
};
int s,t,k; 
int dis[1005];
int vis[1005];
priority_queue <nod> q;
nod tem,temm;
int p[2];
void add(int f,int to,int v,int fl){
    p[fl]++;
    e[p[fl]][fl].ne=head[f][fl];
    e[p[fl]][fl].to=to;
    e[p[fl]][fl].v=v;
    head[f][fl]=p[fl];
    return ;
}
void dij(int now){
        memset(dis,0x3f,sizeof(dis));
        dis[t]=0;
        temm.dis=0;
        temm.po=t;
        temm.di=0;
        q.push((temm));
        while(!q.empty()){
            tem=q.top();
            q.pop();
            if(vis[tem.po]){
                continue; 
            }
            vis[tem.po]++;
            int u=tem.po;
            for(int i=head[u][now];i;i=e[i][now].ne){
                int v=e[i][now].to;
                if(dis[v]>dis[u]+e[i][now].v){
                    dis[v]=dis[u]+e[i][now].v;
                    temm.dis=dis[v];
                    temm.po=v;
                    temm.di=0;
                    q.push(temm );
                }
            }                   
        }
}
void Aimeeeeeeeeee(int now){
    memset(vis,0,sizeof(vis));
    while(!q.empty()){
        q.pop();
    }
        temm.dis=dis[s];
        temm.po=s;
        temm.di=0;
        q.push(temm);
        while(!q.empty()){
            tem=q.top();
            q.pop();
        vis[tem.po]++;
            int u=tem.po;
            if(vis[tem.po]==k&&tem.po==t){
                cout<<tem.di<<endl;
                exit(0); 
                return ;
            }
            if(vis[u]>k)
                continue; 
            for(int i=head[u][now];i;i=e[i][now].ne){
                int v=e[i][now].to;
                    if(vis[v]>=k)
                    continue; 
                temm.dis=tem.di+e[i][now].v+dis[v];
                temm.po=v;
                temm.di=tem.di+e[i][now].v;
                q.push(temm);
            }                   
        }
}
signed main(){
    scanf("%ld%ld",&n,&m);
    for(int i=1;i<=m;++i){
        scanf("%ld%ld%ld",&x,&y,&z);
        add(x,y,z,1);
        add(y,x,z,0);
    }
    scanf("%ld%ld%ld",&s,&t,&k); 
    dij(0);
    if(s==t)
    k++;
    Aimeeeeeeeeee(1); 
    cout<<-1<<endl;
    return 0;
}