-
Notifications
You must be signed in to change notification settings - Fork 0
/
main.c
94 lines (74 loc) · 1.98 KB
/
main.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define MAX_QUADRAS 500
#define INF INT_MAX // tempo de viagem extremamente longo
typedef struct {
int destino;
int minutos;
} Rua;
int quadras;
int ruas;
int matrizAdj[MAX_QUADRAS][MAX_QUADRAS];
void inicializarMatrizAdj() {
for (int i = 0; i < quadras; i++) {
for (int j = 0; j < quadras; j++) {
matrizAdj[i][j] = INF;
}
matrizAdj[i][i] = 0; // 0 na diagonal principal
}
}
void adicionarRua(int a, int b, int minutos) {
matrizAdj[a][b] = minutos;
}
void dijkstra(int origem, int destino) {
int dist[MAX_QUADRAS];
int visitado[MAX_QUADRAS] = {0};
for (int i = 0; i < quadras; i++) {
dist[i] = INF;
}
dist[origem] = 0;
for (int contador = 0; contador < quadras - 1; contador++) {
int u, min_dist = INF;
for (int v = 0; v < quadras; v++) {
if (!visitado[v] && dist[v] < min_dist) {
u = v;
min_dist = dist[v];
}
}
visitado[u] = 1;
for (int v = 0; v < quadras; v++) {
if (!visitado[v] && matrizAdj[u][v] != INF &&
dist[u] + matrizAdj[u][v] < dist[v]) {
dist[v] = dist[u] + matrizAdj[u][v];
}
}
}
if (dist[destino] == INF) {
printf("-1\n");
} else {
printf("%d\n", dist[destino]);
}
}
int main() {
int eventos;
scanf("%d %d %d", &quadras, &ruas, &eventos);
inicializarMatrizAdj();
for (int i = 0; i < ruas; i++) {
int a, b, minutos;
scanf("%d %d %d", &a, &b, &minutos);
adicionarRua(a, b, minutos);
}
for (int i = 0; i < eventos; i++) {
int tipo, a, b;
scanf("%d %d %d", &tipo, &a, &b);
if (tipo == 1) {
int minutos;
scanf("%d", &minutos);
adicionarRua(a, b, minutos);
} else if (tipo == 2) {
dijkstra(a, b);
}
}
return 0;
}