Visit departments

#include <stdio.h>
#define MAX_N 101
#define MAX_STEP 101

int maxStep;
//adjacent list
int adjCnt[MAX_N];
int next[MAX_N][MAX_N];
float weight[MAX_N][MAX_N];

//DP and BFS
int lastVisitedStep[MAX_N];
float changeByStep[MAX_STEP][MAX_N];

//Queue
int verticeQ[20010];
int stepQ[20010];
int front, rear;
int N;


void calculateChange()
{
	//reset DP table
	for (int i = 0; i <= maxStep; i++)
		for (int j = 1; j <= N; j++)
			changeByStep[i][j] = 0;
	changeByStep[0][1] = 1;

	int u, v, step;
	//At step 0, probability of dept 1 is always 1
	front = rear = 0;
	verticeQ[0] = 1;
	stepQ[0] = 0;
	while (front <= rear) {
		u = verticeQ[front];
		step = stepQ[front++];
		for (int i = 0; i < adjCnt[u]; i++) {
			v = next[u][i];
			changeByStep[step + 1][v] += changeByStep[step][u] * weight[u][i]; //update probability of dept "v" at step + 1

			//if next step is exceed max step, don't need to check further
			if (lastVisitedStep[v] < step + 1 && step < maxStep) {
				lastVisitedStep[v] = step + 1;
				verticeQ[++rear] = v;
				stepQ[rear] = step + 1;
			}
		}
	}
}

float maxChange;
int maxIdx;
void findMax(int step)
{
	maxIdx = 0;
	maxChange = 0.0;
	for (int i = 1; i <= N; i++) {
		if (changeByStep[step][i] > maxChange) {
			maxChange = changeByStep[step][i];
			maxIdx = i;
		}
	}
}



int main()
{
	int tc, T = 10;
	int st, en;
	float w;
	int E, K, mTime;
	
	for (tc = 1; tc <= T; tc++) {
		scanf("%d%d%d%d", &N, &E, &K, &mTime);
		for (int i = 1; i < MAX_N; i++) {
			adjCnt[i] = 0;
			lastVisitedStep[i] = 0;
		}
		for (int i = 0; i < E; i++) {
			scanf("%d%d%f", &st, &en, &w);
			next[st][adjCnt[st]] = en;
			weight[st][adjCnt[st]++] = w;
		}

		if (mTime < 10) {
			printf("#%d 1 1.000000 1 1.000000\n", tc);
			continue;
		}

		maxStep = mTime / 10;
		calculateChange();
		findMax(maxStep);
		printf("#%d %d %f ", tc, maxIdx, maxChange);
		findMax((mTime - K) / 10);
		printf("%d %f\n", maxIdx, maxChange);
	}
	return 0;
}