分层图跑最短路。
但是自己还是太不熟练，没看出来。
太弱了。
对于「选择不多于K条路径并将其长度减半」，实际上可以视为：对于一条路径 $ (u,v) $ ，建两条边：一条到达更高一层的v，权值为 $ w/2 $ ；另一条到达同一层的v，权值为 $ w $ 。
可以发现这个路径是层层升高的。
然后，从起点1跑最短路，取所有层的n中的最短路长度的最小值即可。
码：
#include#include #include #include #include using namespace std;int n,m,k;int u[500050],v[500050],w[500050],head[500050],nxt[500050],cnt=0;void add(int ui,int vi,int wi){ cnt++; nxt[cnt]=head[ui]; head[ui]=cnt; u[cnt]=ui; v[cnt]=vi; w[cnt]=wi;}int d[500050];void spfa(){ bool inq[500050]; memset(inq,0,sizeof inq); memset(d,0x3f3f,sizeof d); queue q; d[1]=0; inq[1]=1; q.push(1); while(!q.empty()){ int ui=q.front();q.pop(); for(int i(head[ui]);i;i=nxt[i]){ int vi=v[i],wi=w[i]; if(d[vi]>d[ui]+wi){ d[vi]=d[ui]+wi; if(!inq[vi]){ inq[vi]=1; q.push(vi); } } } }}int main(){ scanf("%d%d%d",&n,&m,&k); for(int i(1);i<=m;i++){ int ui,vi,wi;scanf("%d%d%d",&ui,&vi,&wi); for(int j(0);j<=k-1;j++){ add(ui+j*n,vi+j*n,wi); add(vi+j*n,ui+j*n,wi); add(ui+j*n,vi+(j+1)*n,wi/2); add(vi+j*n,ui+(j+1)*n,wi/2); } add(ui+k*n,vi+k*n,wi); add(vi+k*n,ui+k*n,wi); } spfa(); int ans=d[n]; for(int i(2);i<=k+1;i++)ans=min(ans,d[n*i]); printf("%d",ans); return 0;}
这里有一点要注意，最后检查每一层n的时候，对应的编号是 $ n,n+n,n+2n,n+3n,......n+kn $
所以最后枚举要到k+1