Участник:Easik/GEORGE

Материал из DISCOPAL
Перейти к: навигация, поиск

C / gcc

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h> /* bool */
 
#define INF 1000000000;
 
int main() {
 
    int i, j;
    int N, M;
    int A, B, K, G;
    int inter_a, inter_b, L;
    int pos, tmp_max;
    int graph[1000][1000], edge_cost[1000][1000];
    bool visited_flag[1000];
    int george_path[1000], luka_path[1000];
 
    /* The first line contains two integers N and M (2 <= N <= 1000, 2 <= M <= 10 000), 
        the number of intersections and the number of streets */
    scanf("%d %d", &N, &M);
 
    /* Init Dijkstra (edges) and init graph */
    for (i = 0; i < N; i++) {
 
        for (j = 0; j < N; j++) {
 
            edge_cost[i][j] = INF;
            graph[i][j] = INF;
 
        }
 
    }
 
    /* Other params */
    scanf("%d %d %d %d", &A, &B, &K, &G);
    /* Decrement A, B since they start from 1 */
    A--;
    B--;
 
    /* G integers, the labels of intersections mister George will visit */
    for (i = 0; i < G; i++) {
 
        scanf("%d", &george_path[i]);
        /* Decrement they since they start from 1 */
        george_path[i]--;
 
    }
 
    /* Read */
    for (i = 0; i < M; i++) {
 
        scanf("%d %d %d", &inter_a, &inter_b, &L);
        /* Decrement they since they start from 1 */
        inter_a--;
        inter_b--;
        edge_cost[inter_a][inter_b] = L;
        edge_cost[inter_b][inter_a] = L;
 
    }
 
    /* Timestamp george's path */
    L = 0;
    for (i = 1; i < G; i++) {
 
        graph[george_path[i - 1]][george_path[i]] = L;
        graph[george_path[i]][george_path[i - 1]] = L;
        L += edge_cost[george_path[i - 1]][george_path[i]];
 
    }
 
    /* Init Dijkstra's visited_flag & lukas_path's timestamps */
    for (i = 0; i < N; i++) {
 
        luka_path[i] = INF;
        visited_flag[i] = false;
 
    }
 
    /* Set initial timer offset for Luka */
    luka_path[A] = K;
 
    /* Optimize Luka's path step-by-step */
    for (i = 0; i < N; i++) {
 
        pos = -1;
        for (j = 0; j < N; j++) {
 
            if (visited_flag[j]) continue;
            if (pos == -1 || luka_path[j] < luka_path[pos]) pos = j;
 
        }
        visited_flag[pos] = true;
 
        for (j = 0; j < N; j++) {
 
            /* Luka is frontrunning George */
            if (luka_path[pos] < graph[pos][j]) {
 
                /* Select fastest path */
                luka_path[j] = (luka_path[j] <= edge_cost[pos][j] + luka_path[pos]) ? luka_path[j] : (edge_cost[pos][j] + luka_path[pos]);
 
            /* George is frontrunning Luka */
            } else {
 
                /* Wait for George to pass this edge */
                tmp_max = (luka_path[pos] >= graph[pos][j] + edge_cost[pos][j]) ? luka_path[pos] : (graph[pos][j] + edge_cost[pos][j]);
 
                /* Select fastest path */
                luka_path[j] = (luka_path[j] <= tmp_max + edge_cost[pos][j]) ? luka_path[j] : (tmp_max + edge_cost[pos][j]);
 
            }
 
        }
 
    }
 
    /* Output result: time in path for Luka */
    printf("%d\n", luka_path[B] - luka_path[A]);
 
    return 0;
 
}