-
Notifications
You must be signed in to change notification settings - Fork 0
/
10009_.cpp
101 lines (97 loc) · 2 KB
/
10009_.cpp
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
94
95
96
97
98
99
100
101
#include <cstdio>
#include <iostream>
#include <vector>
#include <bitset>
using namespace std;
int ma[26][26];
int pesos [26][26];
int grado[26]={1};
bitset<26> procesado;
bitset<26> visitado;
vector<int> salida;
bool salir;
void prof (int i, int f) { //inicio, fin
procesado[i]=visitado[i]=1;
salida.push_back(i);
int c,sig;
for (c=0;c<grado[i];c++) {
sig=ma[i][c];
if (sig==f){
salida.push_back(sig);
salir=1;
return;
}else if (!procesado[sig] && !visitado[sig]) {
prof(sig,f);
}if (salir)
return;
}
salida.pop_back();
}
void floyd()
{
int i,j; /* dimension counters */
int k; /* intermediate vertex counter */
int through_k; /* distance through vertex k */
for (k=0; k<26; k++)
for (i=0; i<26; i++)
for (j=0; j<26; j++) {
through_k = pesos[i][k]+pesos[k][j];
if (through_k < pesos[i][j])
pesos[i][j] = through_k;
}
}
int main() {
int blocks,m,n;
char f,c;
scanf("%d\n",&blocks);
while(blocks>0) {
scanf("%d%d",&m,&n);
//printf("b=%d m=%d n=%d\n",blocks,m,n);
for (f=0;f<26;f++) {
for (c=0;c<grado[f];c++)
ma[f][c]=0;
grado[f]=0;
}
while(m>0) {
while (cin>>f && !(f>='A' && f<='Z')) ;
while (cin>>c && !(c>='A' && c<='Z')) ;
f-='A';
c-='A';
ma[f][grado[f]++]=c;
ma[c][grado[c]++]=f;
pesos[f][c]=pesos[c][f]=1;
//printf("%c %c\n",f,c);
m--;
}
for (f=0;f<26;f++){
printf("%c <%d>: ",f+'A',grado[f]);
for (c=0;c<26;c++) {
//printf("%c ",ma[f][c]+'A');
printf("%d ",pesos[f][c]);
}
printf("\n");
}
printf("\n");
floyd();
return 0;
while (n>0) {
salir=0;
procesado.reset();
visitado.reset();
salida.clear();
while (cin>>f && !(f>='A' && f<='Z')) ;
while (cin>>c && !(c>='A' && c<='Z')) ;
prof(f-'A',c-'A');
for (f=0;f<salida.size();f++)
printf("%c",salida[f]+'A');
printf("\n");
n--;
}
do {
c=getchar();
}
while (c!='\n' && c!=EOF);
blocks--;
}
return 0;
}