题意：给定一个T条边的无向图，求S到E恰好经过N条边的最短路径 T≤100 N≤1000000
分析：（据说好像假期学长讲过）
首先很容易想到的是dp[i][j][k]表示从i到j经过k条边的最短路径
显然是会mle以及t的
不过不妨碍我们yy一下这种错误的做法
dp[i][j][k]=min(dp[i][j][k],dp[i][p][k-1]+mapp[p][j]) 其中p是枚举的中间点，mapp是直接连接i与j的边的长度
也就是说i->j走k条边的路径可以转化为i->p走k-1条边再从p走到j的路径
k只与k-1相关，所以可以消一维
也就是dp'[i][j]=max(dp[i][p]+mapp[p][j])
但即便是这样，显然时间也不够，
我们先回到原来的dp[i][j][k]
其实dp[i][j][k]并不是非要从dp[i][j][k-1]转移过来
他其实也可以从dp[i][j][k/2]转移过来
比如dp[i][j][k]=min(dp[i][j][k],dp[i][p][k/2]+dp[p][j][k/2])
当然这里的k/2也可以从k/4转移......
发现没，这是不是只需要用二进制给n拆分一下，再求出每个位数的dp矩阵就行了
这是不是又像极了矩阵快速幂（有没有回忆起假期讲的东西（反正我是没有））
所以只需要用矩阵快速幂即可，只不过把原来行列式的计算改成类似floyd罢了
这题到这里也基本结......
等等，咱dp数组还开不下呢
其实根本没必要开k那维，显然问这个问题还是矩阵快速幂没学好（好像是我自己问的）
现在才是差不多结束了
当然还是有几个细节
比如这里题目的点号范围给的是1e3，但一共才100条边，所以用个map即可，点数最多200个
还有，dp[i][j][1]（当然这里并没有1这维，只是为了方便表达）是什么
就是mapp呗
但注意，这里i到i并不是0，而是inf（不存在）
因为这个dp的定义就是从i到j经过一条边所需的最小距离
i到i显然经过了0条边，自然是inf
最后，我们的矩阵快速幂的当前值肯定有个初始值，
正常矩阵快速幂肯定有个单位矩阵来做初始值，也就是说这个矩阵“乘”任何一个矩阵都是那个矩阵
这里没必要费心思去找这个单位矩阵
只需要把当前值先赋成dp[i][j][1]，再n--即可
代码：
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<map>
using namespace std;
const int maxn=2e2+1;
int num,n;
map<int,int> mapp;
struct Node
{
int dp[maxn][maxn];
friend Node operator * (const Node &x,const Node &y)
{
Node z;
memset(z.dp,0x3f,sizeof(z.dp));
for(int k=1;k<=num;k++) for(int i=1;i<=num;i++) for(int j=1;j<=num;j++) z.dp[i][j]=min(z.dp[i][j],x.dp[i][k]+y.dp[k][j]);
return z;
}
}now,ans;
void chuli()
{
ans=now,n--;
while(n)
{
if(n&1) ans=ans*now;
n>>=1,now=now*now;
}
}
int main()
{
int s,e,t,x,y,z;
scanf("%d%d%d%d",&n,&t,&s,&e);
memset(now.dp,0x3f,sizeof(now.dp));
while(t--)
{
scanf("%d%d%d",&z,&x,&y);
if(!mapp[x]) mapp[x]=++num;
if(!mapp[y]) mapp[y]=++num;
now.dp[mapp[x]][mapp[y]]=z;
now.dp[mapp[y]][mapp[x]]=z;
}
chuli();
printf("%d",ans.dp[mapp[s]][mapp[e]]);
return 0;
}