牛站_牛客网站

牛站_牛客网站链接https://www.acwing.com/problem/content/submission/code_detail/1207146/题目给定一张由T条边构成的无向图,点的编号为1~1

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

链接

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
输入样例:

2 6 6 4
11 4 6
4 4 8
8 4 9
6 6 8
2 6 9
3 8 9

输出样例:

10

思路

假设数组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;
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/168106.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • matlab二分法例题(用二分法求零点例题)

    matlab二分法小题方程y=sinx在区间[-1,2]有唯一实根,若用二分法求根,并要求误差不得超过10^6,需要多少次二分?tol=0.000001;%容差a=-1;%输入两个端点值b=2;ya=feval(@f,a);%把a赋给yayb=feval(@f,b);max=round((log(b-a)-log(tol))/log(2))%最大迭代次数ifyayb>0fprintf(“二分法不适用”)elsefork=1:max%循环c=(a+b)/2yc=feval(

  • nv12转rgb「建议收藏」

    nv12转rgb「建议收藏」nv12格式nv12转rgb两种格式代码voidNV12_T_RGB(unsignedintwidth,unsignedintheight,unsignedchar*Y,unsignedchar*UV,unsignedchar*rgb){ intr,g,b; inty,u,v; for(inti=0;i<height;i++){ for(intj=0;j<width;j++){ y=

  • databus教程_搭建区观察记录表

    databus教程_搭建区观察记录表最近公司因需要同步oracle数据到mysql,调研了Datax对于大数据量的同步代价有些大。开源的databus需要对源码做二次开发,才可以使用,前期我们搭建后,用自带的person表做了测试。确认可行后研发更改了源码。准备工作:1.配制gradle和java2.ojdbc6-11.2.0.2.0.jar放到如下目录:databus-master/sandbox-repo/com/oracle/ojdbc6/11.2.0.2.0/更改defaultEnvironment.gradl

  • 最新海康摄像机、NVR、流媒体服务器、回放取流RTSP地址规则说明[通俗易懂]

    最新海康摄像机、NVR、流媒体服务器、回放取流RTSP地址规则说明[通俗易懂]本文档主要介绍海康威视设备直播预览RTSP、录像回放RTSP、流媒体取流的RTSPURL和IE直接预览、回放的HTTPURL。RTSP为取流协议,取到码流后需要解码显示,可以通过VLC播放器或者EasyPlayer播放器进行测试,IE等浏览器网页不支持RTSP协议直接取流预览或者回放,需要安装OCX插件,这也是目前大部分安防厂家的做法。目前也有很多支持RTSP进行网页无插件直播的流媒…

  • 中缀表达式转后缀表达式栈的变化_利用栈实现中缀转后缀

    中缀表达式转后缀表达式栈的变化_利用栈实现中缀转后缀这里给出中缀表达式转后缀表达式的算法过程,以及再举两个例子算法过程:1.数字直接加入后缀表达式2.如果是‘(’,入栈3.如果是‘)’,则依次把栈中的运算符加入后缀表达式,直到出现‘(’并从栈中删除它4.如果是运算符+-*/a.栈空或者栈顶元素为‘(’,入栈b.高于栈顶元素优先级,入栈c.否则依次弹出栈顶运算符,直到遇到一个优先级小于它的运算符或者是遇到‘(’为止5.遍历完成后,如果栈非空则依次弹出所有栈顶元素加入到表达式当中例1:…

    2022年10月30日
  • 考研复试-数据库面试题[通俗易懂]

    考研复试-数据库面试题[通俗易懂]准备复试时自己从别的博客上复制的一些面试题,因为当时都复制到一个文本文件中了,也不知道从谁的博客上复制的。触发器的作用?答:触发器是一中特殊的存储过程,主要是通过事件来触发而被执行的。它可以强化约束,来维护数据的完整性和一致性,可以跟踪数据库内的操作从而不允许未经许可的更新和变化。可以联级运算。如,某表上的触发器上包含对另一个表的数据操作,而该操作又会导致该表触发器被触发。什么是存储…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号