10269

This can be done two ways using floyed-warshall algorithm and also using bfs;

Floyed warshall:

#include <iostream>
#include <queue>
#include <cstring>

#define INF 1500000

using namespace std;

int gr[105][105];
int A,B,M,L,K;
bool trace[105][15];
int d[105][15];

int shortestpath()
{
	d[A+B][0]=0;
	queue<int> q;

	q.push(A+B);
	q.push(0);
	//trace[A+B][0]=1;
	while(!q.empty())
	{
		int a = q.front();q.pop();
		int boot = q.front();q.pop();
		trace[a][boot]=0;
		for(int i=1;i<=A+B;i++)
		{
			if(i==a)
			continue;
			if(boot<K && gr[a][i]<=L)
			{
				if(d[i][boot+1]>d[a][boot])
				{
					d[i][boot+1] = d[a][boot];
					if(!trace[i][boot+1])
					{
						trace[i][boot+1] = 1;
						q.push(i);q.push(boot+1);
					}
				}

			}
			if(d[i][boot]>d[a][boot]+gr[a][i])
			{
				d[i][boot] = d[a][boot]+gr[a][i];
				if(!trace[i][boot])
				{
					trace[i][boot]=1;
					q.push(i);q.push(boot);
				}
			}
		}
	}

	int MN = INF;
	for(int i=0;i<=K;i++)
	{
		if(MN>d[1][i])
		MN = d[1][i];
	}
	cout<<MN<<"\n";
}

int main()
{
	int t;
	int x,y,z;
	cin>>t;

	while(t--)
	{
		cin>>A>>B>>M>>L>>K;
		for(int i=0;i<105;i++)
			for(int j=0;j<105;j++)
			{
				if(j<15)
				{
					d[i][j]=INF;
					trace[i][j] = false;
				}
				if(i==j)
				gr[i][j] = 0;
				else
				gr[i][j] = INF;
			}


		//cout<<gr[2][4]<<"\n";
		while(M--)
		{
			cin>>x>>y>>z;
			gr[x][y] = z;
			gr[y][x] = z;
		}

		for(int k=1;k<=A;k++)
		{
			for(int i=1;i<=A+B;i++)
			{
				for(int j=1;j<=A+B;j++)
				{
					if(gr[i][k]==INF || gr[k][j]==INF)
					continue;
					if(gr[i][j]>gr[i][k]+gr[k][j])
					gr[i][j] = gr[i][k]+gr[k][j];
				}
			}
		}

		shortestpath();
	}

	return 0;
}

BFS:

#include <iostream>
#include <queue>
#include <cstring>


using namespace std;


int state[105][505][15];//state position,distance can cross by boot(L-cost),no of boot use left
int A,B,M,L,K;
int cost[105][105];


int main()
{
	int t;
	int x,y,z;
	cin>>t;

	while(t--)
	{
		cin>>A>>B>>M>>L>>K;

		memset(cost,-1,sizeof(cost));
		memset(state,63,sizeof(state));
		int INF = state[0][0][0];

		while(M--)
		{
			cin>>x>>y>>z;
			cost[x][y]=z;
			cost[y][x]=z;
		}

		state[A+B][0][K]=0;
		queue<int> q;
		q.push(A+B);q.push(0);q.push(K);

		while(!q.empty())
		{
			int a = q.front();q.pop();
			int l = q.front();q.pop();
			int k = q.front();q.pop();
			int par_cost = state[a][l][k];

			for(int i=1;i<=A+B;i++)
			{
				if(cost[a][i]==-1)
				continue;
				int d = cost[a][i];
				if(a<=A)
				{
					if(l>=d)
					{
						int ll = l-d;
						int aa = i;
						int kk = k;

						if(state[aa][ll][kk]> par_cost)
						{
							state[aa][ll][kk] = par_cost;
							q.push(aa);q.push(ll);q.push(kk);
						}
					}
				}

				if(k>0 && L>=d)
				{
					int ll = L-d;
					int aa = i;
					int kk = k-1;

					if(state[aa][ll][kk]>par_cost)
					{
						state[aa][ll][kk] = par_cost;
						q.push(aa);q.push(ll);q.push(kk);
					}
				}


				if(state[i][0][k]>(par_cost+d))
				{
					state[i][0][k] = (par_cost+d);
					q.push(i);q.push(0);q.push(k);
				}
			}
		}

		int MN = INF;
		for(int i=0;i<=L;i++)
		{
			for(int j=0;j<=K;j++)
			{
				if(state[1][i][j]<MN)
				MN = state[1][i][j];
			}
		}

		cout<<MN<<"\n";
	}

	return 0;
}