oj.uz

Submission #5748

# Submission time Handle Problem Language Result Execution time Memory
5748 2014-05-15T14:34:33 Z model_code 가장 안전한 경로 (TOKI14_safest) C++
100 / 100
 300 ms 74456 KB 
/*
 * Official Solution
 * 
 * Safest Route
 * Derianto Kusuma
 */

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>


#define MAX_VERTEX         2501

#define NO_VERTEX            -1
#define NO_PATH      1000000000


int n_vertex;
int n_edge;
int direct[MAX_VERTEX][MAX_VERTEX];
int start;
int finish;

// Dijkstra tree
int optimal[MAX_VERTEX]; // To finish
int parent[MAX_VERTEX];
int n_child[MAX_VERTEX];
int child[MAX_VERTEX][MAX_VERTEX];

// Blocked and detour distance
int optimal_blocked[MAX_VERTEX]; // To finish, given X-parent(X) blocked
int optimal_out_tree[MAX_VERTEX][MAX_VERTEX]; // Given current context is a node X,
// give the optimal out tree distance from member of X's tree to finish through
// an out tree node.  Or NO_PATH.

// Safe distance
int safe[MAX_VERTEX];



void read_input() {
    scanf("%d %d %d %d", &n_vertex, &n_edge, &start, &finish);
    start--;
    finish--; // Normalize to 0-based
    
    // Init direct distance table
    for (int i = 0; i < n_vertex; i++)
        for (int j = 0; j < n_vertex; j++)
            direct[i][j] = NO_PATH;
    
    int v1, v2, d;
    for (int i = 0; i < n_edge; i++) {
        scanf("%d %d %d", &v1, &v2, &d);
        v1--;
        v2--;
        direct[v1][v2] = d;
        direct[v2][v1] = d;
    }
    
    // DEBUG OK
    /*printf("GRAPH:\n");
    for (int i = 0; i < n_vertex; i++) {
        printf("%d: ", i + 1);
        for (int j = 0; j < n_vertex; j++) {
            if (direct[i][j] == NO_PATH) {
                printf("   .");
            } else {
                printf("%4d", direct[i][j]);
            }
        }
        printf("\n");
    }*/
}

void construct_dijkstra_tree() {
    // Initialize
    for (int i = 0; i < n_vertex; i++)
        optimal[i] = NO_PATH;
    optimal[finish] = 0;
    parent[finish] = NO_VERTEX;
    
    bool closed[MAX_VERTEX];
    for (int i = 0; i < n_vertex; i++) {
        closed[i] = false;
    }
    
    int pivot;
    int best;
    
    // Dijkstra
    while (true) {
        // Choose pivot
        pivot = NO_VERTEX;
        best = NO_PATH;
        for (int i = 0; i < n_vertex; i++) {
            if (!closed[i] && optimal[i] < best) {
                best = optimal[i];
                pivot = i;
            }
        }
        
        if (pivot == NO_VERTEX)
            break;
    
        // Close: parent and child relationship is not modifiable anymore
        closed[pivot] = true;
        if (parent[pivot] != NO_VERTEX)
            child[parent[pivot]][n_child[parent[pivot]]++] = pivot;
        
        for (int next = 0; next < n_vertex; next++) {
            if (!closed[next]) {
                if (optimal[pivot] + direct[pivot][next] < optimal[next]) {
                    optimal[next] = optimal[pivot] + direct[pivot][next];
                    parent[next] = pivot;
                }
            }
        }
        
    }
    
    // DEBUG OK
    /*printf("\n");
    printf("AFTER DIJKSTRA:\n");
    for (int i = 0; i < n_vertex; i++) {
        printf("%3d: optimal:%3d    parent:%3d     child: ", i + 1,
            optimal[i], parent[i] + 1);
        for (int j = 0; j < n_child[i]; j++) {
            printf("%3d", child[i][j] + 1);
        }
        printf("\n");
    }
  
    printf("\n");*/
}


// Add all nodes in the tree to the array with length n
void add_tree(int *n, int *array, int x) {
    array[(*n)++] = x;
    for (int i = 0; i < n_child[x]; i++)
        add_tree(n, array, child[x][i]);
}

// Helper data structure
int n_sibling;
int sibling[MAX_VERTEX];

int n_inner;
int inner[MAX_VERTEX];

// x: vertex in which x's tree is the inner tree and the rest is outer.
void r_compute(int x) {
    if (x == finish) {
        for (int y = 0; y < n_vertex; y++) {
            optimal_out_tree[x][y] = NO_PATH;
        }
        optimal_blocked[x] = NO_PATH;
        
    } else {
        // Initialize optimal_out_tree
        for (int y = 0; y < n_vertex; y++) {
            optimal_out_tree[x][y] = optimal_out_tree[parent[x]][y];
        }
        
        // Get collection of parent + sibling trees
        n_sibling = 0;
        sibling[n_sibling++] = parent[x];
        for (int i = 0; i < n_child[parent[x]]; i++) {
            int c = child[parent[x]][i];
            if (c != x) {
                add_tree(&n_sibling, sibling, c);
            }
        }
        
        // Get inner tree
        n_inner = 0;
        add_tree(&n_inner, inner, x);
        
        // Update optimal_out_tree for all in-tree nodes
        optimal_blocked[x] = NO_PATH;
        int through = NO_VERTEX;
        for (int i = 0; i < n_inner; i++) {
            int y = inner[i];
            for (int j = 0; j < n_sibling; j++) {
                int z = sibling[j];
                if (y != x || z != parent[x]) {
                    if (optimal[z] + direct[z][y] < optimal_out_tree[x][y]) {
                        optimal_out_tree[x][y] = optimal[z] + direct[z][y];
                    }
                }
            }
            
            if (optimal_out_tree[x][y] + optimal[y] - optimal[x] < optimal_blocked[x]) {
                optimal_blocked[x] = optimal_out_tree[x][y] + optimal[y] - optimal[x];
                through = y;
            }
        }
        
        // Determine optimal_blocked

        // DEBUG OK
        /*printf("\n-------------------------------------- R_COMPUTE [%d]\n", x + 1);
        printf("INNER: ");
        for (int i = 0; i < n_inner; i++)
            printf("%d ", inner[i] + 1);
        printf("\nSIBLINGS: ");
        for (int i = 0; i < n_sibling; i++)
            printf("%d ", sibling[i] + 1);
        printf("\nOPTIMAL_OUT_TREE:\n");
        for (int i = 0; i < n_inner; i++) {
            int y = inner[i];
            printf("  [%3d] : %10d\n", y + 1, optimal_out_tree[x][y]);
        }
        printf("OPTIMAL OUT TREE PATH: cost = %d through %d\n", optimal_blocked[x],
            through + 1);*/
        
    }
    
    for (int i = 0; i < n_child[x]; i++)
        r_compute(child[x][i]);
}

void precompute_blocked_distance() {
    r_compute(finish);
}

int max(int a, int b) {
    if (a > b) {
        return a;
    } else {
        return b;
    }
}

void compute_safe_distance() {

    // Initialize
    for (int i = 0; i < n_vertex; i++)
        safe[i] = NO_PATH;
    safe[finish] = 0;
    
    bool closed[MAX_VERTEX];
    for (int i = 0; i < n_vertex; i++) {
        closed[i] = false;
    }
    
    int pivot;
    int best;
    int proposed;
    
    
    // For debugging
    int from[MAX_VERTEX];
    from[finish] = NO_VERTEX;
    
    // Dijkstra
    while (true) {
        // Select pivot
        pivot = NO_VERTEX;
        best = NO_PATH;
        for (int i = 0; i < n_vertex; i++) {
            if (!closed[i] && safe[i] < best) {
                best = safe[i];
                pivot = i;
            }
        }
        
        if (pivot == NO_VERTEX)
            break;
        
        // Close pivot
        closed[pivot] = true;
        
        
        // Update neighbors
        for (int i = 0; i < n_vertex; i++) {
            if (!closed[i]) {
                if (pivot == parent[i]) {
                    proposed = max(optimal_blocked[i], direct[i][pivot] + safe[pivot]);
                } else {
                    proposed = max(optimal[i], direct[i][pivot] + safe[pivot]);
                }
                //printf("pivot = %d, i = %d, proposed = %d\n",
                //    pivot + 1, i + 1, proposed);
                if (proposed < safe[i]) {
                    safe[i] = proposed;
                    from[i] = pivot;
                }
            }
        }
    }
    
    // DEBUG
    /*printf("\nSAFE RESULT:\n");
    for (int i = 0; i < n_vertex; i++) {
        printf("%3d: optimal %10d | blocked %10d | safe %10d | from %3d\n",
            i + 1, optimal[i], optimal_blocked[i], safe[i], from[i] + 1);
    }
    printf("\n");
    
    printf("\nSOLUTION with length %d:\n", safe[start]);
    int curr = start;
    while (curr != finish) {
        printf("%d -> ", curr + 1);
        curr = from[curr];
    }
    printf("%d\n\n", finish + 1);*/
}


void write_output() {
    printf("%d\n", safe[start]);
}

int main() {
    read_input();
    construct_dijkstra_tree();
    precompute_blocked_distance();
    compute_safe_distance();
    write_output();

    return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 74456 KB Output is correct
2 Correct 0 ms 74456 KB Output is correct
3 Correct 0 ms 74456 KB Output is correct
4 Correct 0 ms 74456 KB Output is correct
5 Correct 0 ms 74456 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 74456 KB Output is correct
2 Correct 0 ms 74456 KB Output is correct
3 Correct 0 ms 74456 KB Output is correct
4 Correct 0 ms 74456 KB Output is correct
5 Correct 0 ms 74456 KB Output is correct
6 Correct 0 ms 74456 KB Output is correct
7 Correct 0 ms 74456 KB Output is correct
8 Correct 0 ms 74456 KB Output is correct
9 Correct 0 ms 74456 KB Output is correct
10 Correct 0 ms 74456 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 74456 KB Output is correct
2 Correct 0 ms 74456 KB Output is correct
3 Correct 4 ms 74456 KB Output is correct
4 Correct 0 ms 74456 KB Output is correct
5 Correct 4 ms 74456 KB Output is correct
6 Correct 0 ms 74456 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 74456 KB Output is correct
2 Correct 0 ms 74456 KB Output is correct
3 Correct 24 ms 74456 KB Output is correct
4 Correct 8 ms 74456 KB Output is correct
5 Correct 20 ms 74456 KB Output is correct
6 Correct 8 ms 74456 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 292 ms 74456 KB Output is correct
2 Correct 292 ms 74456 KB Output is correct
3 Correct 300 ms 74456 KB Output is correct
4 Correct 272 ms 74456 KB Output is correct