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
|
#include <iostream>
#include<vector>
#include<stdio.h>
using namespace std;
#define INF 100000;
int dist[1000000];
void addedge(vector<int>graph[],int u, int v){
graph[u].push_back(v);
graph[v].push_back(u);
}
int main()
{
vector<int>graph[100000];
int test = 0;
scanf("%d", &test);
while (test) {
bool visit[100000] = { false };
int tujuan = 0;
int vertices = 0;
int start,end;
int edges = 0;
scanf("%d %d", &aim, &edges);
vertices = edges + 1;
std::fill(dist, dist + vertices+1, 10000000);
for (int i = 1; i <edges+1; i++) { /* in fourth iteration, i need to enter in the end to finish last test case why?? */
start=0;
end=0;
scanf("%d %d", &start, &end);
addedge(graph,start,end);
}
dist[1] = 0;
for (int i = 1; i < vertices; i++) {
if (visit[i] == true)
continue;
else
visit[i] = true;
int y = graph[i].size();
for (int k = 0; k < graph[i].size(); k++) {
if (dist[graph[i][k]] > dist[i] + 1)
dist[graph[i][k]] = dist[i] + 1;
}
}
cout << dist[aim]<<"\n";
test--;
}
return 0;
}
|