Skip to content

Instantly share code, notes, and snippets.

@PedroRacchetti
Created April 28, 2020 18:33
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save PedroRacchetti/c803a796fc696981d293a15228706680 to your computer and use it in GitHub Desktop.
Save PedroRacchetti/c803a796fc696981d293a15228706680 to your computer and use it in GitHub Desktop.
#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