Wide delivery

/* Copyright 2003   R. Civalero   L.G.P.L.
   Modifi� par Franck Rousseau et Simon Nieuviarts
   Inspir� du fichier list.h de Linux

	queue.h : Gestion de files g�n�riques avec priorit�
	          A priorit� �gale, comportement FIFO.

	Elle est impl�ment�e par une liste circulaire doublement
	chain�e. La file est tri�e par ordre croissant de priorit�
	lors de l'ajout. Donc l'�l�ment prioritaire qui doit sortir
	en premier est le dernier de la liste, c'est � dire l'�l�ment
	pr�c�dent la t�te de liste.

	Pour cr�er une file :
	 1) Cr�er une t�te de liste de type 'link',
	 2) L'initialiser avec LIST_HEAD_INIT,
	 3) APRES les avoir cr�es, ajouter des �lements dans la file
	    avec la macro queue_add,
	Les �l�ments doivent �tre des structures contenant au moins un
	champ de type 'link' et un champ de type 'int' pour la priorit�.

	Pour utiliser la file :
	 - Supprimer des �l�ments particulier avec la macro queue_del,
	 - R�cuperer et enlever de la file l'�lement prioritaire avec
	   la macro queue_out,
	 - Ajouter d'autre �l�ments avec la macro queue_add,
	 - Tester si la file est vide avec la fonction queue_empty

	Attention : certains pointeurs pointent vers des �l�ments des
	            files, alors que d'autres pointent vers le champ
		    du lien de chainage de ces �l�ments.
		    Les t�tes de file/liste sont des liens de chainage
		    de type 'link' et non des �l�ments.
*/

#include <stddef.h>
#include <assert.h>
#include <sys/queue.h>

/**
 * Type structure pour faire les liens de chainage
 */
typedef struct list_link {
	struct list_link *prev;
	struct list_link *next;
} link;

/**
 * Initialisation d'une t�te de liste (t�te de file).
 */
#define LIST_HEAD_INIT(name) { &(name), &(name) }
#define INIT_LIST_HEAD(ptr) do { struct list_link *__l = (ptr); __l->next = __l; __l->prev = __l; } while (0)

/**
 * Initialisation d'un maillon de liste.
 *
 * Si vous pensez en avoir besoin, il est fort probable que ce soit une erreur.
 * Les zones m�moires donn�es par l'allocateur ou allou�es � la compilation
 * sont initialis�es � 0 (respectivement par l'allocateur et par le crt0).
 */
#define INIT_LINK(ptr) do { struct list_link *__l = (ptr); __l->next = 0; __l->prev = 0; } while (0)

/**
 * Ajout d'un �l�ment dans la file avec tri par priorit�
 * ptr_elem  : pointeur vers l'�l�ment � chainer
 * head      : pointeur vers la t�te de liste
 * type      : type de l'�l�ment � ajouter
 * listfield : nom du champ du lien de chainage
 * priofield : nom du champ de la priorit�
 */
#define queue_add(ptr_elem, head, type, listfield, priofield)                 \
	do {                                                                  \
		link *__cur_link=head;                                        \
		type *__elem = (ptr_elem);                                    \
		link *__elem_link=&((__elem)->listfield);                     \
                assert((__elem_link->prev == 0) && (__elem_link->next == 0)); \
		do  __cur_link=__cur_link->next;                              \
	   	while ( (__cur_link != head) &&                               \
		        (((queue_entry(__cur_link,type,listfield))->priofield)\
	     	               < ((__elem)->priofield)) );                    \
	   	__elem_link->next=__cur_link;                                 \
	   	__elem_link->prev=__cur_link->prev;                           \
	   	__cur_link->prev->next=__elem_link;                           \
	   	__cur_link->prev=__elem_link;                                 \
	} while (0)

/**
 * Macro � usage interne utilis�e par la macro queue_add
 * R�cup�ration du pointeur vers l'objet correspondant
 *   (On calcule la diff�rence entre l'adresse d'un �l�ment et l'adresse
 *   de son champ de type 'link' contenant les liens de chainage)
 * ptr_link  : pointeur vers le maillon
 * type      : type de l'�l�ment � r�cup�rer
 * listfield : nom du champ du lien de chainage
 */
#define queue_entry(ptr_link, type, listfield) \
	((type *)((char *)(ptr_link)-(unsigned long)(&((type *)0)->listfield)))


/**
 * Tester si une file est vide
 * head : pointeur vers la t�te de liste
 * retourne un entier (0 si pas vide)
 */
static __inline__ int queue_empty(link *head)
{
	return (head->next == head);
}


/**
 * Retrait de l'�l�ment prioritaire de la file
 * head      : pointeur vers la t�te de liste
 * type      : type de l'�l�ment � retourner par r�f�rence
 * listfield : nom du champ du lien de chainage
 * retourne un pointeur de type 'type' vers l'�l�ment sortant
 */
#define queue_out(head, type, listfield) \
	(type *)__queue_out(head,(unsigned long)(&((type *)0)->listfield))

/**
 * Fonction � usage interne utilis�e par la macro ci-dessus
 * head : pointeur vers la t�te de liste
 * diff : diff�rence entre l'adresse d'un �l�ment et son champ de
 *        type 'link' (cf macro list_entry)
 */
static __inline__ void *__queue_out(link *head, unsigned long diff)
{
	//On r�cup�re un pointeur vers le maillon
	//du dernier �l�ment de la file.
	unsigned long ptr_link_ret=(unsigned long)(head->prev);

	//Si la file est vide, on retourne le pointeur NULL.
	if (queue_empty(head)) return ((void *)0);

	//Sinon on retire l'�l�ment de la liste,
	head->prev=head->prev->prev;
	head->prev->next=head;

	((link *)ptr_link_ret)->prev = 0;
	((link *)ptr_link_ret)->next = 0;

	//Et on retourne un pointeur vers cet �l�ment.
	return ((void *)(ptr_link_ret-diff));
}


/**
 * Suppression d'un �l�ment dans la file
 * ptr_elem  : pointeur vers l'�l�ment � supprimer
 * listfield : nom du champ du lien de chainage
 */
#define queue_del(ptr_elem, listfield)                                       \
	do {                                                                 \
		link *__elem_link=&((ptr_elem)->listfield);                  \
                assert((__elem_link->prev != 0) && (__elem_link->next != 0)); \
		__elem_link->prev->next=__elem_link->next;                   \
	   	__elem_link->next->prev=__elem_link->prev;                   \
                __elem_link->next = 0;                                       \
                __elem_link->prev = 0;                                       \
	} while (0)


/**
 * Parcours d'une file
 * ptr_elem  : pointeur vers un �l�ment utilis� comme it�rateur de boucle
 * head      : pointeur vers la t�te de liste
 * type      : type des �l�ments de la liste
 * listfield : nom du champ du lien de chainage
 */
#define queue_for_each(ptr_elem, head, type, listfield)                      \
	for (ptr_elem = queue_entry((head)->next,type,listfield);            \
             &ptr_elem->listfield != (head);                                 \
             ptr_elem = queue_entry(ptr_elem->listfield.next,type,listfield))


/**
 * Parcours d'une file en sens inverse
 * ptr_elem  : pointeur vers un �l�ment utilis� comme it�rateur de boucle
 * head      : pointeur vers la t�te de liste
 * type      : type des �l�ments de la liste
 * listfield : nom du champ du lien de chainage
 */
#define queue_for_each_prev(ptr_elem, head, type, listfield)                 \
	for (ptr_elem = queue_entry((head)->prev,type,listfield);            \
             &ptr_elem->listfield != (head);                                 \
             ptr_elem = queue_entry(ptr_elem->listfield.prev,type,listfield))


/**
 * Recuperer un pointeur vers l'element prioritaire de la file
 * sans l'enlever de la file.
 * head : pointeur vers la t�te de liste
 * type : type de l'�l�ment � retourner par r�f�rence
 * listfield : nom du champ du lien de chainage
 * retourne un pointeur de type 'type' vers l'�l�ment prioritaire
 */
#define queue_top(head, type, listfield) \
(type *)__queue_top(head,(unsigned long)(&((type *)0)->listfield))

/**
 * Fonction � usage interne utilis�e par la macro ci-dessus
 * head : pointeur vers la t�te de liste
 * diff : diff�rence entre l'adresse d'un �l�ment et son champ de
 * type 'link' (cf macro list_entry)
 */
static __inline__ void *__queue_top(link *head, unsigned long diff)
{
	//On r�cup�re un pointeur vers le maillon
	//du dernier �l�ment de la file.
	unsigned long ptr_link_ret=(unsigned long)(head->prev);

	//Si la file est vide, on retourne le pointeur NULL.
	if (queue_empty(head)) return ((void *)0);

	//Sinon retourne un pointeur vers cet �l�ment.
	return ((void *)(ptr_link_ret-diff));
}


/**
 * Recuperer un pointeur vers l'element le moins prioritaire de la file
 * sans l'enlever de la file.
 * head : pointeur vers la t�te de liste
 * type : type de l'�l�ment � retourner par r�f�rence
 * listfield : nom du champ du lien de chainage
 * retourne un pointeur de type 'type' vers l'�l�ment prioritaire
 */
#define queue_bottom(head, type, listfield) \
(type *)__queue_bottom(head,(unsigned long)(&((type *)0)->listfield))

/**
 * Fonction � usage interne utilis�e par la macro ci-dessus
 * head : pointeur vers la t�te de liste
 * diff : diff�rence entre l'adresse d'un �l�ment et son champ de
 * type 'link' (cf macro list_entry)
 */
static __inline__ void *__queue_bottom(link *head, unsigned long diff)
{
	//On recupere un pointeur vers le maillon
	//du premier element de la file.
	unsigned long ptr_link_ret=(unsigned long)(head->next);

	//Si la file est vide, on retourne le pointeur NULL.
	if (queue_empty(head)) return ((void *)0);

	//Sinon retourne un pointeur vers cet element.
	return ((void *)(ptr_link_ret-diff));
}



#define LIST_HEAD_INIT_PROC(x) assert(!"utiliser INIT_LIST_HEAD au lieu de LIST_HEAD_INIT_PROC")
#include <stdint.h>
#include <stdlib.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>



typedef struct road{
    uint64_t dest;
    uint64_t w;
    SLIST_ENTRY(road) l;
} road;

SLIST_HEAD(list, road);

typedef struct city{
    uint64_t name;
    uint64_t w;
    link l;
} city;

uint64_t min2(uint64_t a, uint64_t b){
    return a<b? a : b;
}

int main() {
    uint64_t n = 0;
    uint64_t m = 0;
    if (scanf("%ld %ld", &n, &m) == 0)
        return EXIT_FAILURE;

    list *roads = (list *) malloc(n * sizeof(list));
    uint64_t *cities = (uint64_t *) calloc(n, sizeof(uint64_t));

    // main algo
    for (uint64_t i = 0; i < n; i++){
        SLIST_INIT(roads+i);
    }
    // printf("1\n");
    uint64_t a, b, w;
    road *r;
    for (uint64_t i = 0; i < m; i++){
        if (scanf("%ld %ld %ld", &a, &b, &w) == 0)
            return EXIT_FAILURE;
        a--;b--;
        r = (road*) malloc(sizeof(road));
        r->dest = b;
        r->w = w;
        SLIST_INSERT_HEAD(roads+a, r, l);
        r = (road*) malloc(sizeof(road));
        r->dest = a;
        r->w = w;
        SLIST_INSERT_HEAD(roads+b, r, l);
    }
    // printf("2\n");

    link lc;
    INIT_LIST_HEAD(&lc);
    city *c = (city*) malloc(sizeof(city));
    c->name = 0;
    c->w=9999999999;

    queue_add(c, &lc, city, l, w);
    while (!queue_empty(&lc)){
        // printf("3\n");
        c = queue_out(&lc, city, l);
        if (c->w <= cities[c->name])
            continue;
        cities[c->name] = c->w;
        SLIST_FOREACH(r, roads + c->name, l){
            city *nc = (city*) malloc(sizeof(city));
            nc->name = r->dest;
            nc->w = min2(r->w, c->w);
            queue_add(nc, &lc, city, l, w);
        }
    }
    for (uint64_t i = 1; i < n; i++){
        printf("%ld ", cities[i]);
    }
    printf("\n");



    return EXIT_SUCCESS;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: ACCEPTED

Test 19

Verdict: ACCEPTED

Test 20

Verdict: ACCEPTED

Test 21

Verdict: ACCEPTED

Test 22

Verdict: ACCEPTED

Test 23

Verdict: ACCEPTED

Test 24

Verdict: ACCEPTED

Test 25

Verdict: ACCEPTED

Test 26

Verdict: ACCEPTED

Test 27

Verdict: ACCEPTED

Test 28

Verdict: ACCEPTED

Test 29

Verdict: ACCEPTED

Test 30

Verdict: ACCEPTED

Test 31

Verdict: ACCEPTED

Test 32

Verdict: ACCEPTED

Test 33

Verdict: ACCEPTED

Test 34

Verdict: ACCEPTED

Test 35

Verdict: ACCEPTED

Test 36

Verdict: ACCEPTED

Test 37

Verdict: ACCEPTED

Test 38

Verdict: ACCEPTED

Test 39

Verdict: ACCEPTED

Test 40

Verdict: ACCEPTED

Test 41

Verdict: ACCEPTED

Test 42

Verdict: ACCEPTED

Test 43

Verdict: ACCEPTED

Test 44

Verdict: ACCEPTED

Test 45

Verdict: ACCEPTED

Test 46

Verdict: ACCEPTED

Test 47

Verdict: ACCEPTED

Test 48

Verdict: ACCEPTED

Test 49

Verdict: ACCEPTED

Test 50

Verdict: ACCEPTED

Test 51

Verdict: ACCEPTED

Test 52

Verdict: ACCEPTED

Test 53

Verdict: ACCEPTED

Test 54

Verdict: ACCEPTED

Test 55

Verdict: ACCEPTED

Test 56

Verdict: ACCEPTED

Test 57

Verdict: ACCEPTED

Test 58

Verdict: ACCEPTED

Test 59

Verdict: ACCEPTED

Test 60

Verdict: TIME LIMIT EXCEEDED

Test 61

Verdict: TIME LIMIT EXCEEDED

Test 62

Verdict: TIME LIMIT EXCEEDED

Test 63

Verdict: TIME LIMIT EXCEEDED

Test 64

Verdict: TIME LIMIT EXCEEDED

Test 65

Verdict: TIME LIMIT EXCEEDED

Test 66

Verdict: TIME LIMIT EXCEEDED

Test 67

Verdict: TIME LIMIT EXCEEDED

Test 68

Verdict: TIME LIMIT EXCEEDED

Test 69

Verdict: ACCEPTED