题目描述
给定一张由T条边构成的无向图,点的编号为1~1000之间的整数。
求从起点S到终点E恰好经过N条边(可以重复经过)的最短路。
输入格式
第1行:包含四个整数N,T,S,E。
第2..T+1行:每行包含三个整数,描述一条边的边长以及构成边的两个点的编号。
输出格式
输出一个整数,表示最短路的长度。
数据范围
2≤T≤100
,
2≤N≤106
样例
输入样例:
2 6 6 4
11 4 6
4 4 8
8 4 9
6 6 8
2 6 9
3 8 9
输出样例:
10
算法1
yoho ~
写在前面
(((如果您们不太会矩阵快速幂的话请右转百度一下,蒟蒻我不知道还有没有写矩乘的博客或题解的时间了呢~~
这道题的话,借助了机房大佬们的人类智慧,蒟蒻我终于把这道题码了出来,这道题的思路很巧妙呢~(据说和DDP思路一样呢~,当然,蒟蒻我不会跟您们讲的,因为我也不会啊~~~~)
step 1:
首先如果没有边数限制那就是SPFA或DIJ裸题。
但是如果考虑到边数限制,因为可以一条边走多次,考虑到上面两种算法,事实上可能需要记录用多少步走到每一个点的最小代价,当然,这样的空间复杂度我们是不能接受的,然后考虑下面的问题
step 2:
思考一波,发现最短路算法里还有个floyed!!!
然后把它拿出来(emmm
发现这个算法的本质就是在枚举k的时候,我们已经求出了每两个点之间(可能)经过1~k-1内的点的最短路,
然后我们大力强迫他每一次转移都多经过一个点,也就是对于每一个点的dis值,每一次新的转移只可能是再多经过一个k点,也就是多增加一条边得到,这样我们就可以通过两个矩阵转移n次得到答案了呢~(???突然矩阵???,好吧,是下面这样的)
step 3
事实上,学过矩阵快速幂的同学们可能会发现floyed的转移方程即 dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
是不是长得挺想矩乘的转移方程的~
没错,我们矩乘就是这么优秀,他还可以转移min或max值,只要将转移方程由d[i][j]=d[i][j]+d[i][k]*d[k][j];
变成d[i][j]=min/max(d[i][j],d[i][k]+d[k][j]);对于这道题的话当然是取min
于是我们就可以矩阵加速了
step 4
了解矩阵快速幂的同学们应该知道,矩阵快速幂最难的是构造转移矩阵,这东西在这道题里直接就上dis数组即可,(dis[i][i]=0;dis[i][j]=min(inf,val[i][j]))(就是你怎么初始化floyed里的dis就怎么初始化他就行了)
初始矩阵的话我们只用第一行即可(f[1][i]表示已经借助矩阵转移了x次,也就是经过x条边,到i的最短路径是多少)
于是就做完了。。。。。。
易错点
1.要注意矩乘不满足交换律(额,但是本题的这种矩乘的话它得满足结合律,只有这样我们才能保证正确性)
2.点太多了所以我们要大力李三花(离散化)点的编号(当然大佬们可以用map但是不比我毒瘤快多少呢~)
3.emmmmm???
时间复杂度
T就看作不同的点的数量吧
大概是T^2*log(n)
C++ 代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
int x=0;int f=1;char c=getchar();
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
return x*f;
}
const int maxn = 250;
const int inf = 0x3f3f3f3f;
struct node{
int d[maxn][maxn];
};
node st,f,ee;
int n,m,s,e,cnt;
void init(){
for(int i=1;i<=cnt;i++){
for(int j=1;j<=cnt;j++){
if(i==1){
if(j!=s) st.d[i][j]=inf;
else st.d[i][j]=0;
}
else st.d[i][j]=0;
}
}
}
node mul(node a,node b){
node res;
for(int i=1;i<=cnt;i++){
for(int j=1;j<=cnt;j++){
res.d[i][j]=inf;
for(int k=1;k<=cnt;k++){
res.d[i][j]=min(res.d[i][j],a.d[i][k]+b.d[k][j]);
}
}
}
return res;
}
node pow(node a,int b){
node res=a;b--;
while(b){
if(b&1) res=mul(res,a);
a=mul(a,a);
b>>=1;
}
return res;
}
struct xxx{
int u,v,w;
}edge[40000];
int num[40000];
signed main(){
n=read();m=read();s=read();e=read();
memset(f.d,0x3f,sizeof(f.d));
cnt=0;
for(int i=1;i<=m;i++){
int w=read();int u=read();int v=read();
edge[i].u=u;edge[i].v=v;edge[i].w=w;
num[++cnt]=u;num[++cnt]=v;
}
sort(num+1,num+1+cnt);
cnt=unique(num+1,num+1+cnt)-num-1;
for(int i=1;i<=m;i++){
int u=lower_bound(num+1,num+1+cnt,edge[i].u)-num;
int v=lower_bound(num+1,num+1+cnt,edge[i].v)-num;
f.d[u][v]=f.d[v][u]=min(f.d[u][v],edge[i].w);
}
s=lower_bound(num+1,num+1+cnt,s)-num;
e=lower_bound(num+1,num+1+cnt,e)-num;
init();
node ans=mul(st,pow(f,n));
printf("%lld",ans.d[1][e]);
return 0;
}