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
|
#include <iostream>
#include <vector>
#include <stdio.h>
#include <string.h>
#include <queue>
#define SIZE 100000
using namespace std;
typedef pair<int, int> k;
vector<int>v[SIZE];
int dist[SIZE];
int visit[SIZE];
bool vis[SIZE];
int main()
{
int test, tujuan, edge, awal, akhir;
scanf("%d", &test);
while (test) {
scanf("%d %d", &tujuan, &edge);
for (int i = 0; i < edge; i++) {
scanf("%d %d\n", &awal, &akhir); /*stuck here in last iteration */
v[awal].push_back(akhir);
v[akhir].push_back(awal);
memset(vis, false, sizeof vis);
std::fill(dist, dist + edge + 2, 10000000);
}
dist[1] = 0;
priority_queue<k, vector<k>, greater<k> >s;
s.push(make_pair(0, 1));
while (!s.empty()) {
k baru = s.top();
s.pop();
int dis = baru.first;
int node = baru.second;
if (vis[node])continue;
vis[node] = true;
for (int i = 0; i < v[node].size(); i++) {
int e = v[node][i];
if (dist[e] > dis + 1) {
dist[e] = dis + 1;
s.push(make_pair(dist[e], e));
}
}
}
cout << dist[tujuan] << "\n";
test--;
}
return 0;
}
|