【题意】给定m条边的无向图，起点s，终点t，要求找出s到t恰好经过n条边的最短路径。n<=10^6,m<=100。
【算法】floyd+矩阵快速幂
【题解】
先对点离散化，得到点数N。
对初始边建立初始矩阵，然后考虑每次多跑一条边相当于一次矩阵乘法，即c[i][j]=min(a[i][k],a[k][j]),k=1~N。
定义了矩阵乘法，就可以用矩阵快速幂优化了。
初始矩阵ans[i][i]=0，转移矩阵a[i][i]=inf，这样就是恰好n条边。（如果a[i][i]=0就是<=n条边）
复杂度O(N^3*log n)。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
using namespace std;
const int N=;//Òª¿ªÁ½±¶¡£
typedef int mat[N][N];
mat a,c,ans;
int n,m,s,t,cnt=,z[];
int read()
{
char c;int s=,t=;
while(!isdigit(c=getchar()))if(c=='-')t=-;
do{s=s*+c-'';}while(isdigit(c=getchar()));
return s*t;
}
void mul(mat a,mat b){
memset(c,0x3f,sizeof(c));
for(int i=;i<=cnt;i++){
for(int j=;j<=cnt;j++){//iºÍjÒ»ÑùÒ²ÊÇ¿ÉÒÔÈÆһȦ»ØÀ´µÄ¡£
for(int k=;k<=cnt;k++)c[i][j]=min(c[i][j],a[i][k]+b[k][j]);
}
}
for(int i=;i<=cnt;i++)for(int j=;j<=cnt;j++)a[i][j]=c[i][j];
}
int main(){
n=read();m=read();s=read();t=read();
memset(a,0x3f,sizeof(a));
for(int i=;i<=m;i++){
int w=read(),u=read(),v=read();//ȨֵÔÚµÚһλ£¡£¡£¡
if(!z[u])z[u]=++cnt;if(!z[v])z[v]=++cnt;
u=z[u];v=z[v];
a[u][v]=a[v][u]=min(a[u][v],w);
}
memset(ans,0x3f,sizeof(ans));
for(int i=;i<=cnt;i++)ans[i][i]=;
while(n){
if(n&)mul(ans,a);
mul(a,a);
n>>=;
}
printf("%d",ans[z[s]][z[t]]);
return ;
}