https://run.codes/offerings/view/926

paa-crush.c

/*
	Trabalho PAA - Crush
	Menor caminho com Dijkstra
	Autor: Pedro Henrique Lara Campos (UFSCar RA 726578)
	Data: 2018-11-21
	https://run.codes/exercises/view/9772
*/
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<limits.h>

#define dprintf(...) //fprintf(stderr, __VA_ARGS__)

unsigned short vrt_num;
unsigned int edg_num;

typedef struct _Neighbor {
	unsigned short who;
	unsigned char weight;
	struct _Neighbor *next;
} Neighbor;

typedef struct _Vert {
	bool visited;
	bool first_set;
	unsigned int weight;
	struct _Vert *prev;
	Neighbor *edges;
} Vert;

Vert *verts;

void add_edge(unsigned short a, unsigned short b, unsigned char w) {
	Neighbor *edge = (Neighbor*) malloc(sizeof(Neighbor));
	Vert *vert = &verts[a];
	*edge = (Neighbor){b, w, vert->edges};
	vert->edges = edge;
}

Vert *pop_vert(Vert *q) {
	Vert *r, *e = &verts[vrt_num], *n = NULL;
	unsigned int min_dist = UINT_MAX;
	for(r = verts; r < e; r++)
		if (!r->visited && r->first_set && r->weight < min_dist) {
			min_dist = r->weight;
			n = r;
		}
	return n;
}

int main() {
	if(scanf("%hu %u", &vrt_num, &edg_num) != 2)
		return -1;

	verts = (Vert*) calloc(sizeof(Vert), vrt_num);

	unsigned short a, b;
	unsigned char w;
	while(scanf("%hu %hu %hhu", &a, &b, &w) == 3) {
		add_edge(a, b, w);
	}

	verts->first_set = true;
	// THESE ARE NOT NEEDED WITH CALLOC :)
	//verts->weight = 0;
	//verts->prev = NULL;

	Vert *q=&verts[0], *n;
	Neighbor *u;
	unsigned int new_weight;
	do {
		q->visited = true;
		u = q->edges;

		if(u != NULL)
			do {
				dprintf("Visiting edge %u to %hu: %hhu\n", q-verts, u->who, u->weight);
				n = &verts[u->who];
				new_weight = q->weight + u->weight;
				if(!n->first_set || new_weight < n->weight) {
					n->weight = new_weight;
					n->prev = q;
					n->first_set = true;
					dprintf("\t%hu is now child of %u with %u\n", n-verts, q-verts, n->weight);
				}
			} while ((u = u->next) != NULL);
	} while((q = pop_vert(q)) != NULL);

	dprintf("Ended with: ");
	printf("%hu\n", verts[vrt_num-1].weight);

	// LET the OS FREE EVERYTHING AT ONCE :)
	//free(edges)
	return 0;
}

paa-debate.c

/*
	Trabalho PAA - Debate
	Grafos bi-partidos
	Autor: Pedro Henrique Lara Campos (UFSCar RA 726578)
	Data: 2018-11-21
	https://run.codes/exercises/view/9771
*/
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<limits.h>

#define dprintf(...) //fprintf(stderr, __VA_ARGS__)

unsigned short stu_num;

typedef enum {
	gr_undf=0,
	gr_a,
	gr_b
} Group;

typedef struct _Neighbor {
	unsigned short who;
	struct _Neighbor *next;
} Neighbor;

typedef struct _Vert {
	bool visited;
	Group group;
	Neighbor *edges;
} Vert;

Vert *verts;

void add_edge(Vert *vert, unsigned short b) {
	Neighbor *edge = (Neighbor*) malloc(sizeof(Neighbor));
	*edge = (Neighbor){b, vert->edges};
	vert->edges = edge;
}

Neighbor *queue = NULL;

void queue_vert(unsigned short who) {
	Neighbor *edge = (Neighbor*) malloc(sizeof(Neighbor));
	*edge = (Neighbor){who, NULL};
	if(queue == NULL) {
		queue = edge;
		dprintf("\t\tInit guy: %hu\n", who);
	} else {
		Neighbor *qi=queue;
		while (qi->next != NULL) {
			if(qi->who == who) {
				dprintf("\t\tRepeated guy: %hu\n", who);
				return;
			}
			qi = qi->next;
		}
		if(qi->who != who) {
			qi->next = edge;
			dprintf("\t\tNew guy: %hu\n", who);
		} else {
			dprintf("\t\tLast guy was our guy: %hu\n", who);
		}
	}
}

Vert *unque_vert() {
	if(queue == NULL)
		return NULL;
	unsigned short who = queue->who;
	dprintf("Poping %hu\n", who);
	//free(queue);
	queue = queue->next;
	return &verts[who];
}

int main() {
	if(scanf("%hu", &stu_num) != 1)
		return -1;
	dprintf("We have %hu\n", stu_num);

	verts = (Vert*) calloc(sizeof(Vert), stu_num);
	Vert *vi, *ve=&verts[stu_num];

	unsigned short z, b;

	for(vi=verts; vi<ve; vi++) {
		if(scanf("%hu", &z) != 1)
			break;
		while(z > 0) {
			if(scanf("%hu", &b) != 1)
				return 0;
			add_edge(vi, b);
			z--;
		}
	}
	dprintf("We added everybody!\n");

	vi=&verts[0];
	vi->group = gr_a;

	Neighbor *u;
	Vert *n;
	do {
		dprintf("Visiting %u (Group %c)\n", vi-verts,
			(vi->group == gr_undf ? '?' : (vi->group == gr_a ? 'A' : 'B'))
			);
		vi->visited = true;
		u = vi->edges;
		do {
			dprintf("\tAsking %hu\n", u->who);
			n = &verts[u->who];
			if(!n->visited)
				queue_vert(u->who);
			if(n->group == gr_undf) {
				n->group = (vi->group == gr_a ? gr_b : gr_a);
				dprintf("\tSetting group %u <- %c\n", n-verts,
					(n->group == gr_undf ? '?' : (n->group == gr_a ? 'A' : 'B'))
					);
			} else if(vi->group == n->group) {
				puts("Impossivel");
				return 0;
			}
		} while((u = u->next) != NULL);
	} while((vi = unque_vert()) != NULL);

	puts("Vai la, tio Willian!");
	return 0;
}