axuhongbo的个人博客

   题目链接：https://nanti.jisuanke.com/t/A1958  
   原题目：https://acm.taifua.com/bzoj/p/2763.html
   题意：n 个点 m 条有向边，可以让其中不超过 k 条边的边权为 0，问从 1 到 n 的最短路径。
   https://blog.csdn.net/axuhongbo/article/details/82289535
   
   	分层图最短路，把图拆成k+1层，然后每个点拆成k+1个点，这样就有1e6个点，对着1e6个点进行最短路的计算，
堆优化的Dijkstra，O（m+n）logn，大概是1e7的时间复杂度是可以过的！
	我们把每个点都拆成k个层次点，每个相同层次的点按输入的边权连接，每个点可以向它能连接到的点的
下一个层次连接一条边权为0的边；
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
int n,m,k;
int head[3200000],tot;
long long dis[3200000];
struct node{
	int u,v,w,nxt;
}edge[3200000*2];
int vis[3000000];
void addedge(int u,int v,int w){
	edge[tot].u=u;
	edge[tot].v=v;
	edge[tot].w=w;
	edge[tot].nxt=head[u];
	head[u]=tot++;
}
struct node2{
	int u;
	long long dis;
	bool operator < (node2 b) const{
		return dis>b.dis;
	}
};
void dij(int x){
	dis[x]=0;
	priority_queue<node2> s;
	node2 c;
	c.u=x;
	c.dis=dis[x];
	memset(vis,0,sizeof vis);
	s.push(c);
	while(!s.empty()){
		c=s.top();
		s.pop();
		if(vis[c.u])continue;
		vis[c.u] = 1;
		for(int i=head[c.u];~i;i=edge[i].nxt){
			int v=edge[i].v;
			int w=edge[i].w;
			if(dis[v]>dis[c.u]+w){
				dis[v]=dis[c.u]+w;
				node2 e;
				e.u=v;
				e.dis=dis[v];
				s.push(e);
			}
		}
	}
}
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		scanf("%d%d%d",&n,&m,&k);
		memset(dis,0x7f7f7f7f,sizeof dis);
		memset(head,-1,sizeof head);
		tot=0;
		for(int i=1;i<=m;i++){
//			int
			long long u,v,w;
			scanf("%lld %lld %lld",&u,&v,&w);
			for(int j=0;j<=k;j++){
				addedge(u+n*j,v+n*j,w);
				//addedge(v+n*j,u+n*j,w);
				if(j!=k)
                    addedge(u+n*j,v+n*(j+1),0);
			}
//			for(int j=0;j<=k-1;j++)
		}
	    dij(1);
//	    for(int i=1;i<=tot;i++){
//             cout<<edge[i].v<<" "<<edge[i].w<<" "<<edge[i].nxt<<endl;
//	    }
	    long long  maxn=0x3f3f3f3f;
	    for(int i=0;i<=k;i++){
//	        cout<<"*";
//            cout<<dis[i*n+n]<<" ";
	    	maxn = min(maxn,dis[i*n+n]);
		}
		//cout<<endl;
		printf("%lld\n",maxn);
	}
	return 0;
}