牛站_牛客网站

牛站_牛客网站链接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)


相关推荐

  • python安装jieba库的具体步骤_无法安装lxml库

    python安装jieba库的具体步骤_无法安装lxml库Jupternotebook安装jieba库教程jieba库是一款优秀的Python第三方中文分词库,jieba支持三种分词模式:精确模式、全模式和搜索引擎模式,下面是三种模式的特点。精确模式:试图将语句最精确的切分,不存在冗余数据,适合做文本分析 全模式:将语句中所有可能是词的词语都切分出来,速度很快,但是存在冗余数据 搜索引擎模式:在精确模式的基础上,对长词再次进行切分jieba库是第三方库,我们需要单独进行安装,以下提供两种方法:第一种方法:在jupyternoteboo

  • 打开phpstorm 的terminal 工具框的快捷键 alt+F12

    打开phpstorm 的terminal 工具框的快捷键 alt+F12

    2021年10月17日
  • html获取contextpath,JavaScript中${pageContext.request.contextPath}取值问题及解决方案[通俗易懂]

    html获取contextpath,JavaScript中${pageContext.request.contextPath}取值问题及解决方案[通俗易懂]在JSP里取${pageContext.request.contextPath},方式一是可以正常取到,但方式二却取到的是字符“${pageContext.request.contextPath}”方式一:vart=”${pageContext.request.contextPath}”;方式二:jqGrid.js:functionjqGridInclude(){vart=”${pa…

  • pip安装geopandas 教程「建议收藏」

    附上geopandas安装的官网链接(英文):http://geopandas.org/install.html本文安装方式:pipinstallgeopandas系统环境:win1064位python版本:3.7.064位首先需要手动安装geopandas的依赖库:numpy(pipinstall即可,已有不必再安装)six(pipinstall即可…

  • Liquibase的简单使用[通俗易懂]

    Liquibase的简单使用[通俗易懂]`LiquiBase`是一个用于数据库重构和迁移的开源工具,通过日志文件的形式记录数据库的变更,然后执行日志文件中的修改,将数据库更新或回滚到一致的状态。它的目标是提供一种数据库类型无关的解决方案,通

  • ASP.NET和MSSQL高性能分页

    首先是存储过程,只取出我需要的那段数据,如果页数超过数据总数,自动返回最后一页的纪录:setANSI_NULLSONsetQUOTED_IDENTIFIERONGO–===========

    2021年12月20日

发表回复

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

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