# Visit departments

Ann
c_cpp
a year ago
2.0 kB
0
Indexable
Never
```#include <stdio.h>
#define MAX_N 101
#define MAX_STEP 101

int maxStep;
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++) {
lastVisitedStep[i] = 0;
}
for (int i = 0; i < E; i++) {
scanf("%d%d%f", &st, &en, &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;
}```