题目大意：
有n个点的连通图，有m次可以将某一条边权值减半的机会。
不同的机会可以叠加作用于同一条边。
求1~n的最短路。
思路：
拆点，记录1到每个点在使用不同次数的机会后的最短路，然后直接跑Dijkstra即可。
#include<cstdio>
#include<cctype>
#include<vector>
#include<functional>
#include<ext/pb_ds/priority_queue.hpp>
inline int getint() {
register char ch;
while(!isdigit(ch=getchar()));
register int x=ch^'';
while(isdigit(ch=getchar())) x=(((x<<)+x)<<)+(ch^'');
return x;
}
const double inf=1e9;
const int V=,M=;
struct Edge {
int to;
double w;
};
std::vector<Edge> e[V];
inline void add_edge(const int &u,const int &v,const double &w) {
e[u].push_back((Edge){v,w});
}
struct Vertex {
double dis;
int id,k;
bool operator > (const Vertex &another) const {
return dis>another.dis;
}
};
int n,m,s,t;
double d[V][M];
__gnu_pbds::priority_queue<Vertex,std::greater<Vertex> > q;
__gnu_pbds::priority_queue<Vertex,std::greater<Vertex> >::point_iterator p[V][M];
inline void dijkstra() {
for(register int i=;i<=n;i++) {
for(register int j=;j<=m;j++) {
p[i][j]=q.push((Vertex){d[i][j]=(i==s&&j==)?:inf,i,j});
}
}
while(q.top().dis!=inf) {
const Vertex x=q.top();
for(register unsigned i=;i<e[x.id].size();i++) {
const Edge &y=e[x.id][i];
for(register int i=;i<=m-x.k;i++) {
if(x.dis+y.w/(<<i)<d[y.to][x.k+i]) {
q.modify(p[y.to][x.k+i],(Vertex){d[y.to][x.k+i]=x.dis+y.w/(<<i),y.to,x.k+i});
}
}
}
q.modify(p[x.id][x.k],(Vertex){inf,,});
}
}
int main() {
n=getint(),m=getint();
s=,t=n;
for(register int i=;i<=n;i++) {
for(register int j=;j<=n;j++) {
const int w=getint();
if(w) add_edge(i,j,w);
}
}
dijkstra();
printf("%.2f\n",d[t][m]);
return ;
}