Created
April 28, 2020 18:33
-
-
Save PedroRacchetti/c803a796fc696981d293a15228706680 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <bits/stdc++.h> | |
using namespace std; | |
const int maxn = 512; | |
vector<pair<int, int> > grafo[maxn]; //guardaremos no grafo a vértice | |
//em que cada aresta liga, e sua linha | |
int t, l, o, d, dist[maxn]; | |
void bfs(int x) { | |
memset(dist, 0x3f3f3f3f, sizeof dist); //Inicializando distancia como "infinito" | |
dist[x] = 1; | |
deque<pair<int, int> > fila; | |
for(int i = 0; i < grafo[x].size(); i++){ | |
int v = grafo[x][i].first, linha = grafo[x][i].second; | |
dist[v] = 1; | |
fila.push_back(make_pair(v, linha)); | |
} | |
while (!fila.empty()) { | |
int u = fila.front().first; | |
int linhaatual = fila.front().second; | |
fila.pop_front(); | |
for(int i = 0; i < (int)grafo[u].size(); i++) { | |
int v = grafo[u][i].first; | |
int linha = grafo[u][i].second; | |
int d; | |
if(linha != linhaatual) d = 1; //se temos que trocar de linha, o peso deve ser 1 | |
else d = 0; //caso contrário, deve ser 0 | |
if(dist[v] > dist[u] + d) { | |
dist[v] = dist[u] + d; | |
if(d == 1) fila.push_back(make_pair(v, linha)); // Caso a distancia seja 1, insere o vertice normalmente na fila | |
else fila.push_front(make_pair(v, linha)); // Caso seja 0, insere como prioridade. | |
} | |
} | |
} | |
} | |
int main(){ | |
scanf("%d %d %d %d", &t, &l, &o, &d); | |
for(int i = 0; i < l; i++){ | |
int k; | |
scanf("%d", &k); | |
int ultk; | |
scanf("%d", &ultk); | |
for(int j = 1; j < k; j++){ | |
//conectaremos o ultimo terminal no atual, e vice versa | |
int v; | |
scanf("%d", &v); | |
grafo[ultk].push_back(make_pair(v, i)); | |
grafo[v].push_back(make_pair(ultk, i)); | |
} | |
} | |
bfs(o); //iniciaremos a BFS no vértice O | |
printf("%d\n", dist[d]); // Imprimimos quantas linhas tivemos que usar. | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment