参考双向bfs中extend函数的做法，每次把当前queue中的所有元素扩展一遍，假设原queue中所有节点为正好走过k步被更新的节点，那么新queue中的节点均为k+1步的。

#include<bits/stdc++.h>
using namespace std;

const int N = 505;
int d[N],backup[N],n,m,k;
bool vis[N];
queue<int>q;

struct edge{
    int v,w;
};
vector<edge>e[N];

void extend()
{
    memcpy(backup,d,sizeof d);
    memset(vis,0,sizeof vis);

    int sz = q.size();
    while(sz--)
    {
        int u = q.front();
        q.pop();

        int v,w;
        for(auto [v,w]:e[u])
        {
            if(d[v]>backup[u] + w)
            {
                d[v] = backup[u] + w;
                if(!vis[v])
                {
                    q.push(v);
                    vis[v] = true;
                }
            }
        }
    }
}

void spfa()
{
    q.push(1);

    memset(d,0x3f,sizeof d);
    d[1] = 0;

    for(int t = 0 ; t < k ; t ++)
        extend();
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m >> k;
    while(m--)
    {
        int a,b,c; cin >> a >> b >> c;
        e[a].push_back({b,c});
    }

    spfa();

    if(d[n]==0x3f3f3f3f) cout << "impossible";
    else cout << d[n];

    return 0;
}