ACM-ICPC 2018 南京赛区网络预赛-L-Magical Girl Haze-（分层最短路）

题目链接：https://nanti.jisuanke.com/t/31001

There are NN cities in the country, and MM directional roads from uu to v(1\le u, v\le n)v(1≤u,v≤n). Every road has a distance c_ici​. Haze is a Magical Girl that lives in City 11, she can choose no more than KK roads and make their distances become 00. Now she wants to go to City NN, please help her calculate the minimum distance.

Input

The first line has one integer T(1 \le T\le 5)T(1≤T≤5), then following TT cases.

For each test case, the first line has three integers N, MN,M and KK.

Then the following MM lines each line has three integers, describe a road, U_i, V_i, C_iUi​,Vi​,Ci​. There might be multiple edges between uu and vv.

It is guaranteed that N \le 100000, M \le 200000, K \le 10N≤100000,M≤200000,K≤10,
0 \le C_i \le 1e90≤Ci​≤1e9. There is at least one path between City 11 and City NN.

Output

For each test case, print the minimum distance.

样例输入复制

1
5 6 1
1 2 2
1 3 4
2 4 3
3 4 1
3 5 6
4 5 2

样例输出复制

3

题目来源

ACM-ICPC 2018 南京赛区网络预赛

题目大意：给出T组测试样例，n个城市，m条路（有向图），可以将k个路的距离设置为0

之后是条路，每条路是a->b 距离是l；

找到从1到n的距离最短的那条路，输出长度；

一个相似的题，洛谷P2939，改改数据就行了；

ac：

#include<stdio.h>
#include<string.h>  
#include<math.h>  
  
//#include<map>   
//#include<set>
#include<deque>  
#include<queue>  
#include<stack>  
#include<bitset> 
#include<string>  
#include<fstream>
#include<iostream>  
#include<algorithm>  
using namespace std;  

#define ll long long  
//#define max(a,b) (a)>(b)?(a):(b)
//#define min(a,b) (a)<(b)?(a):(b) 
#define clean(a,b) memset(a,b,sizeof(a))// 水印 
//std::ios::sync_with_stdio(false);
const int MAXN=1e5+10;
const int INF=0x3f3f3f3f;
const ll mod=1e9+7;

struct node{
	int v,nxt;
	ll w;
	node(int _v=0,ll _w=0,int _nxt=0):
    v(_v),w(_w),nxt(_nxt){}
}edge[MAXN<<2];
int head[MAXN],ecnt;
ll dis[MAXN][110];//MAXN点，100层 
int vis[MAXN][110];
int n,m,k;
void intt()
{
	clean(dis,INF);
	clean(vis,0);
	clean(head,-1);
	ecnt=0;
}
void add(int u,int v,ll w)
{
	edge[ecnt]=node(v,w,head[u]);
	head[u]=ecnt++;
}
/*---上面的是板子，不用动---*/
void djstr()
{
	dis[1][0]=0;
	priority_queue<pair<int,pair<int,int> > > que;
	que.push(make_pair(0,make_pair(1,0)));
	while(que.size())
	{
		while(vis[que.top().second.first][que.top().second.second]
		&&que.size()>0)
			que.pop();
		pair<int,int> p=que.top().second;
		vis[p.first][p.second]=1;
		for(int i=head[p.first];i+1;i=edge[i].nxt)
		{
			int temp=edge[i].v;
			//同层查找 
			if(vis[temp][p.second]==0
			&&dis[temp][p.second]>dis[p.first][p.second]+edge[i].w)
			{
				dis[temp][p.second]=dis[p.first][p.second]+edge[i].w;
				que.push(make_pair(-dis[temp][p.second],make_pair(temp,p.second)));
			}
			//下层查找 
			if(p.second+1<=k&&vis[temp][p.second+1]==0
			&&dis[temp][p.second+1]>dis[p.first][p.second])
			{
				dis[temp][p.second+1]=dis[p.first][p.second];
				que.push(make_pair(-dis[temp][p.second+1],make_pair(temp,p.second+1)));
			}
		}
	}
}

int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		intt();
		scanf("%d%d%d",&n,&m,&k);
		int a,b;
		ll l;
		for(int i=1;i<=m;++i)
		{
			scanf("%d%d%lld",&a,&b,&l);
			add(a,b,l);
		}
		djstr();
		printf("%lld\n",dis[n][k]);
	}
}