给定一张由T条边构成的无向图，点的编号为 1∼1000 之间的整数。

求从起点 S 到终点 E 恰好经过 N 条边（可以重复经过）的最短路。

第 11 行：包含四个整数 N，T，S，E。

第 2..T+1 行：每行包含三个整数，描述一条边的边长以及构成边的两个点的编号。

2≤T≤100,
2≤N≤1e6

这里提供三种解法

1.类floyed+快速幂



#include<iostream>

#include<cstring>

#include<map>



using namespace std;



const int N=210;



int res[N][N],g[N][N];

int k,n,m,S,E;

map<int,int> id;



void mul(int c[][N],int a[][N],int b[][N])

{

    static int temp[N][N];

    memset(temp,0x3f,sizeof temp);

    for(int k=1;k<=n;k++)

        for(int i=1;i<=n;i++)

            for(int j=1;j<=n;j++)

                temp[i][j]=min(temp[i][j],a[i][k]+b[k][j]);

    memcpy(c,temp,sizeof temp);

}



void qmi()

{

    memset(res,0x3f,sizeof res);

    for(int i=1;i<=n;i++) res[i][i]=0;//经过0条边

    while(k)//更新的过程

    {

        if(k&1) mul(res,res,g);//res=res*g;根据k决定是否用当前g的结果去更新res

        mul(g,g,g);//g=g*g;g的更新

        k>>=1;

    }

}



int main()

{

    cin>>k>>m>>S>>E;//虽然点数较多，但由于边数少，所以我们实际用到的点数也很少，可以使用map来离散化来赋予

    //他们唯一的编号

    memset(g,0x3f,sizeof g);

    //这里我们来解释一下为什么不去初始化g[i][i]=0呢？

    //我们都知道在类Floyd算法中有严格的边数限制，如果出现了i->j->i的情况其实在i->i中我们是有2条边的

    //要是我们初始化g[i][i]=0,那样就没边了，影响了类Floyd算法的边数限制！

    if(!id.count(S)) id[S]=++n;

    if(!id.count(E)) id[E]=++n;

    S=id[S],E=id[E];

    while(m--)

    {

        int a,b,c;

        scanf("%d%d%d",&c,&a,&b);

        if(!id.count(a)) id[a]=++n;

        if(!id.count(b)) id[b]=++n;

        a=id[a],b=id[b];

        g[a][b]=g[b][a]=min(g[a][b],c);

    }

    qmi();

    cout<< res[S][E] <<endl;

    return 0;

}

完整题解：https://www.acwing.com/solution/content/17209/



2.Bellman - Ford

#pragma GCC optimize(2)

#include <cstdio>

#include <iostream>

#include <algorithm>

#include <cmath>

#include <cstring>

using namespace std;

const int N = 205, M = 105;

struct Edge{

    int u, v, w;

}e[M];

int m, n, s, t, adj[N], dis[N], bDis[N], tot;

void inline read(int &x) {

    x = 0;

    char s = getchar();

    while(s > '9' || s < '0') s = getchar();

    while(s <= '9' && s >= '0') x = x * 10 + s - '0', s = getchar();

}

int inline get(int &x) {

    return lower_bound(adj + 1, adj + 1 + tot, x) - adj;

}



int inline bellmanFord(){

    memset(dis, 0x3f, sizeof dis);

    dis[s] = 0;

    for(register int i = 1; i <= n; i++){

        memcpy(bDis, dis, sizeof dis);

        memset(dis, 0x3f, sizeof dis);

        for(register int j = 1; j <= m; j++){

            dis[e[j].v] = min(dis[e[j].v], bDis[e[j].u] + e[j].w);

            dis[e[j].u] = min(dis[e[j].u], bDis[e[j].v] + e[j].w);

        }

    }

    return dis[t];

}







int main(){

    read(n); read(m); read(s); read(t);

    for (register int i = 1; i <= m; i++) {

        read(e[i].w); read(e[i].u); read(e[i].v);

        adj[++tot] = e[i].u;

        adj[++tot] = e[i].v;

    }

    sort(adj + 1, adj + 1 + tot);

    tot = unique(adj + 1, adj + 1 + tot) - adj - 1;

    for (register int i = 1; i <= m; i++) {

        e[i].u = get(e[i].u), e[i].v = get(e[i].v);

    }

    s = get(s), t = get(t);

    printf("%d\n", bellmanFord());

    return 0;

}



3.倍增 + Floyd 

用倍增的思想，把NN拆成二进制下的多个11，我们把每个‘1′‘1′最短路搞出来，然后拼出来最终的最短路，先预处理：



d[i][j][l]d[i][j][l] 表示从 ii 到 jj 恰好经过 2l2l 条边的最短路。



初始化 d[i][j][0]=w[i][j]d[i][j][0]=w[i][j]，剩下为正无穷（注意是恰好 NN 条边，所以 d[i][i][0]d[i][i][0] 也是非法状态）



转移也很好想：



d[i][j][l]=min(d[i][k][l−1]+d[k][j][l−1])d[i][j][l]=min(d[i][k][l−1]+d[k][j][l−1])，对于一个状态 d[i][j][l]d[i][j][l]，枚举中间点 kk 即可，所以预处理复杂度 O(T3∗log2N)O(T3∗log2N)

接下来用二进制拼起来就行辣~，设 g[i]g[i] 为这前几部走完后，从 ss 到 ii 的最短路， f[i]f[i] 为当前到 ii 的最短路，与保卫王国的拼凑法思想差不多，即：



f[i]=min(g[j]+d[j][i][c])f[i]=min(g[j]+d[j][i][c]) 若 NN 的二进制第 cc 位为 11。

#include <cstdio>

#include <iostream>

#include <algorithm>

#include <cmath>

#include <cstring>

using namespace std;

const int N = 205, M = 105;

struct Edge{

    int u, v, w;

}e[M];

int m, n, s, t, adj[N], tot, d[N][N][20], f[N], g[N];

int L;



int inline get(int x) {

    return lower_bound(adj + 1, adj + 1 + tot, x) - adj;

}

int main(){

    memset(d, 0x3f, sizeof d);

    scanf("%d%d%d%d", &n, &m, &s, &t);

    L = log2(n);

    for (int i = 1; i <= m; i++) {

        scanf("%d%d%d", &e[i].w, &e[i].u, &e[i].v);

        adj[++tot] = e[i].u;

        adj[++tot] = e[i].v;

    }

    sort(adj + 1, adj + 1 + tot);

    tot = unique(adj + 1, adj + 1 + tot) - adj - 1;

    for (int i = 1; i <= m; i++) {

        int u = get(e[i].u), v = get(e[i].v), w = e[i].w;

        d[u][v][0] = d[v][u][0] = min(d[u][v][0], w);

    }

    s = get(s), t = get(t);



    for (int c = 1; c <= L; c++) {

        for (int i = 1; i <= tot; i++) {

            for (int j = 1; j <= tot; j++) {

                for (int k = 1; k <= tot; k++) {

                    d[i][j][c] = min(d[i][j][c], d[i][k][c - 1] + d[k][j][c - 1]);

                }

            }

        }

    }



    memset(g, 0x3f, sizeof g);

    g[s] = 0;

    for (int c = 0; c <= L; c++) {

        if(n >> c & 1) {

            memset(f, 0x3f, sizeof f);

            for (int i = 1; i <= tot; i++) 

                for (int j = 1; j <= tot; j++)

                    f[i] = min(f[i], g[j] + d[j][i][c]);

            memcpy(g, f, sizeof g);

        }

    }

    printf("%d\n", f[t]);

    return 0;

}



完整链接：https://www.acwing.com/solution/content/6111/

算法竞赛进阶指南