没想到“最多经过k条边”恰恰符合Bellman-Ford的性质。。wtcl

先是想到二分最短距离，然后求最小的边数与k比较，但由于并不是经过边数最少就是最短的，所以我设f[u][pk]:1->u，恰经过pk条边的最短距离，用bfs实现最后求出$min${$dis[n][pk]|pk\in [0,k]$}，然后。。就不用二分了

Q：时间复杂度？
A：。。其实我也不是很确定，一开始想状态是$O(n^2)$个，那复杂度也就$O(n^2)$,但写完之后发现。。这咋跟SPFA似的。。
于是时间复杂度就变成玄学了（可见代码）

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
typedef int ll;
typedef std::pair<ll,ll> pll;
#define MAXN 511
#define MAXM 10011
struct Edge
{
    ll v,w,nxt;
}e[MAXM];
ll cnt=0,last[MAXN];
void adde(ll u,ll v,ll w)
{
    ++cnt;
    e[cnt].v=v,e[cnt].w=w;
    e[cnt].nxt=last[u];last[u]=cnt;
}

ll n,m,k,dis[MAXN][MAXN];
bool inq[MAXN][MAXN];
std::queue<pll>q;
void bfs(ll s)
{
    memset(dis,0x3f,sizeof dis);
    dis[s][0]=0;
    q.push(pll(s,0));
    while(!q.empty())
    {
        ll u=q.front().first,pk=q.front().second;q.pop();
        inq[u][pk]=0;
        if(pk>=k)continue;
        for(ll i=last[u];i;i=e[i].nxt)
        {
            ll v=e[i].v;
            if(dis[v][pk+1]>dis[u][pk]+e[i].w)
            {
                dis[v][pk+1]=dis[u][pk]+e[i].w;
                if(!inq[v][pk+1])
                {
                    inq[v][pk+1]=1;
                    q.push(pll(v,pk+1));
                }
            }
        }
    }
}
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for(ll i=1;i<=m;++i)
    {
        ll u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        adde(u,v,w);
    }
    bfs(1);
    ll ans=0x3f3f3f3f;
    for(ll i=0;i<=k;++i)ans=std::min(ans,dis[n][i]);
    if(ans==0x3f3f3f3f)puts("impossible");
    else printf("%d\n",ans);
    return 0;
}