一般就是走的步数在k步内，或者恰好是k步

有边数限制的最短路

如果k比较小

大体有两种实现方法：

Bellman_Ford 直接每一次都把能走的边都走一次，一共重复k次

#include <bits/stdc++.h>
using namespace std;
const int N=505;
const int M=1e4+5;

int u[M],v[M],w[M],tot;

int n,m,k;
int dis1[N],dis2[N];
int solve() {
    for(int i=1;i<=n;i++)dis1[i]=1e9;
    dis1[1]=0;
    for(int i=1;i<=k;i++) {
        for(int j=1;j<=n;j++)dis2[j]=dis1[j];
        //for(int j=1;j<=n;j++)dis1[j]=1e9;//如果加上这一句，那就是必须走k的最短路，而不是k步之内
        //这里应该都能看懂，也就是在上一步的基础上进行走图，dp的思想
        for(int j=1;j<=m;j++)
            dis1[v[j]]=min(dis1[v[j]],dis2[u[j]]+w[j]);
    }
    return dis1[n];
}

int main() {
    cin>>n>>m>>k;
    for(int i=1;i<=m;i++)
        cin>>u[i]>>v[i]>>w[i];
    int ans=solve();
    if(ans>=5e8)cout<<"impossible\n";
    //因为有负边权，所以判断的时候需要特殊处理一下
    else cout<<ans<<endl;
    return 0;
}

spfa算法（因为有负权值，所以只能spfa）

直接记录在当前节点，走了几步的最优解（也就是记录所有可能的状态）

#include <bits/stdc++.h>
using namespace std;
using pii=pair<int,int>;
const int inf=0x3f3f3f3f;
const int N=505;
const int M=1e4+5;

int h[N],ne[M],e[M],w[M],tot;
void add(int from,int to,int wi) {
    e[++tot]=to;
    w[tot]=wi;
    ne[tot]=h[from];
    h[from]=tot;
}

int dis[N][N];
bool vis[N][N];
int n,m,k;
void spfa() {
    queue<pii>q;
    memset(dis,0x3f,sizeof(dis));
    dis[1][0]=0;
    q.push({1,0});
    vis[1][0]=1;
    while(!q.empty()) {
        auto [now,cnt]=q.front();
        q.pop();
        vis[now][cnt]=0;
        if(cnt==k)continue;
        for(int i=h[now];i;i=ne[i]) {
            int to=e[i];
            if(dis[to][cnt+1]>dis[now][cnt]+w[i]) {
                dis[to][cnt+1]=dis[now][cnt]+w[i];
                if(vis[to][cnt+1]==0)q.push({to,cnt+1}),vis[to][cnt+1]=1;
            }
        }
    }
}
//有负边，需要使用spfa

int main() {
    cin>>n>>m>>k;
    for(int i=1;i<=m;i++) {
        int x,y,wi;
        cin>>x>>y>>wi;
        add(x,y,wi);
    }
    spfa();
    int ans=inf;
    for(int i=0;i<=k;i++)ans=min(ans,dis[n][i]);
    //如果是k条边，直接取dis[n][k]就行了
    if(ans==inf)cout<<"impossible\n";
    else cout<<ans<<endl;
    return 0;
}

k较大

用矩阵加速（只适用点数比较少）

P2886 [USACO07NOV]Cow Relays G

#include <bits/stdc++.h>
using namespace std;
const int M=1e6+5;

int id[M];
int n,m,st,ed,tot;
struct mat {//个人矩阵快速幂的习惯性写法
    int a[505][505];
    mat(){memset(a,0x3f,sizeof(a));}
    int* operator[](int x){return a[x];}
    mat operator*(const mat b) {
        mat c;
        for(int k=1;k<=tot;k++)
        for(int i=1;i<=tot;i++)
        for(int j=1;j<=tot;j++)
        c[i][j]=min(c[i][j],a[i][k]+b.a[k][j]);
        return c;
    }
};

mat kpow(mat a,int b) {
    b--;
    mat ans=a;
    //因为这个底数是不好确定的，也就是你不好确定矩阵里面的 1 应该是什么
    //所以这里这里先减去1，然后用a来作为底数
    //也就类似于1乘上  2的10次方，也就等价于2 乘上2的9次方
    while(b) {
        if(b&1)ans=ans*a;
        b>>=1;
        a=a*a;
    }
    return ans;
}

int main() {
    cin>>n>>m>>st>>ed;
    mat dis,ans;
    while(m--) {
        int w,x,y;
        cin>>w>>x>>y;
        if(id[x]==0)id[x]=++tot;
        if(id[y]==0)id[y]=++tot;
        dis[id[x]][id[y]]=dis[id[y]][id[x]]=w;
    }//矩阵初始化
    ans=kpow(dis,n);
    cout<<ans[id[st]][id[ed]];
    return 0;
}
//大致就是只要是有递推公式的题目
//都可以用矩阵来加速
//不懂的，可以先去理解一下矩阵快速幂，然后回头看

结语：其他的也不懂了，如果还有在补充吧

原文地址：http://www.cnblogs.com/basicecho/p/16879317.html