Visit departments
Ann
c_cpp
2 years ago
2.0 kB
7
Indexable
#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; }
Editor is loading...