牛站_牛客网站

全栈程序员站长

发布于 2022-09-20 10:42:19

3930

发布于 2022-09-20 10:42:19

文章被收录于专栏：全栈程序员必看

链接

https://www.acwing.com/problem/content/submission/code_detail/1207146/

题目

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

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

注意: 数据保证一定有解。

输入格式第1行：包含四个整数N，T，S，E。

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

输出格式输出一个整数，表示最短路的长度。

数据范围 2≤T≤100, 2≤N≤10^6 输入样例：

输出样例：

思路

假设数组d[a][i][k]表示i到j的走a条边的最短路,d[b][k][j]表示i到j的走b条边的最短路，那么两者组合就可以得到i到j经过a+b条边的最短路。用flody算法需要把点的编号离散在[1,100]之间。通过枚举边数和k,i,j，时间复杂度太大了。则可以通过快速乘法的思想计算。初始时g[i][j]表示任何两个点经过1条边的最短路，res表示任何两个点经过0条边的最短路。对于m条边的要求，通过快速乘法的中做加法运算得到。加法计算时，通过新开一个临时数组记录a+b条边的答案，不要影响经过a,b条边的值。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=110;
map<int,int> ids;
int g[N][N],n,tmp[N][N],res[N][N];
void add(int a[][N],int b[][N]){
    memset(tmp,0x3f,sizeof tmp);
    for(int k=1;k<=n;++k){
        for(int i=1;i<=n;++i){
            for(int j=1;j<=n;++j){
                tmp[i][j]=min(tmp[i][j],a[i][k]+b[k][j]);//只更新了tmp数组
            }
        }
    }memcpy(a,tmp,sizeof tmp);
}
void qmi(int k){
    memset(res,0x3f,sizeof res);
    for(int i=1;i<=n;++i) res[i][i]=0;//经过0条边只可以到自己
    while(k){
        if(k&1) add(res,g);
        add(g,g);
        k/=2;
    }
}
int main(){
    int k,m,S,T;
    n=0;
    cin>>k>>m>>S>>T;
    memset(g,0x3f,sizeof g);
    ids[S]=++n;ids[T]=++n;
    for(int i=1;i<=m;++i){
        int c,a,b;
        cin>>c>>a>>b;
        if(!ids.count(a)) ids[a]=++n;
        if(!ids.count(b)) ids[b]=++n;
        g[ids[a]][ids[b]]=g[ids[b]][ids[a]]=c;
    }
    qmi(k);
    cout<<res[ids[S]][ids[T]]<<endl;
    return 0;
}

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/168106.html原文链接：https://javaforall.cn

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

如有侵权请联系 cloudcommunity@tencent.com 删除

https