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;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/168106.html原文链接：https://javaforall.net
