终于把它Y出来了 QwQ
题目描述
给定一张由T条边构成的无向图,点的编号为1~1000之间的整数。
求从起点S到终点E恰好经过N条边(可以重复经过)的最短路。
输入样例
2 6 6 4
11 4 6
4 4 8
8 4 9
6 6 8
2 6 9
3 8 9
输出样例
10
C++ 代码
//#pragma GCC optimize(3,"inline","Ofast","fast-math","no-stack-protector","unroll-loops")
//#pragma GCC target("sse","sse2","sse3","sse4","avx","avx2","popcnt")
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#define RG register
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
const int N=2e2+10;
int n,m,s,e,k;
int g[N][N],ad[N*N],res[N][N],luck[N][N];
bool vis[N*N];
inline ll min(int x,ll y)
{
return x>y ? y:x;
}
inline void fast_pow()
{
memset(res,0x3f,sizeof(res));
for (int i=1;i<N;i++) res[i][i]=0;
for (;k;k>>=1)
{
memset(luck,0x3f,sizeof(luck));
if(k&1)
{
for (int p=1;p<=n;p++)
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
luck[i][j]=min(luck[i][j],(ll)res[i][p]+(ll)g[p][j]);
memcpy(res,luck,sizeof(res));
}
memset(luck,0x3f,sizeof(luck));
for (int p=1;p<=n;p++)
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
luck[i][j]=min(luck[i][j],(ll)g[i][p]+(ll)g[p][j]);
memcpy(g,luck,sizeof(g));
}
printf("%d\n",res[ad[s]][ad[e]]);
}
int main()
{
scanf("%d%d%d%d",&k,&m,&s,&e);
memset(g,0x3f,sizeof(g));
for (int i=1;i<=m;i++)
{
int x,y,z;
scanf("%d%d%d",&z,&x,&y);
if(!vis[x]) ad[x]=++n,vis[x]=1;
if(!vis[y]) ad[y]=++n,vis[y]=1;
x=ad[x],y=ad[y];
g[x][y]=(z>g[x][y] ? g[x][y]:z);
g[y][x]=g[x][y];
}
fast_pow();
return 0;
}
/*
倍增+floyd
*/