AC_Code
1 #include <iostream> 2 #include <cstdio> 3 #include <ctime> 4 #include <algorithm> 5 #include <string> 6 #include <cstring> 7 #include <bits/stdc++.h> 8 typedef long long ll; 9 10 const int maxn = 100100; 11 const ll INF = 1e18+9; 12 using namespace std; 13 14 ll x[maxn],y[maxn]; 15 vector<pair<ll,ll> >v[maxn]; 16 priority_queue<pair<ll,ll> >Q; 17 ll n,m; 18 ll length[maxn]; 19 20 int dij(){ 21 22 ll i; 23 for(i=0;i<=n;i++){ 24 v[i].clear(); 25 length[i] = INF; 26 } 27 28 for(i=1; i<=m; i++){ 29 v[x[i]].push_back(make_pair(y[i],1)); 30 v[y[i]].push_back(make_pair(x[i],1)); 31 } 32 Q.push(make_pair(0,1)); 33 length[1] = 0; 34 35 while( !Q.empty()){ 36 ll a, b, c, d; 37 a = Q.top().second; 38 b = Q.top().first; 39 Q.pop(); 40 for( i=0;i<v[a].size(); i++){ 41 c = v[a][i].first; 42 d = v[a][i].second; 43 if( length[c]>length[a]+d ){ 44 length[c] = length[a]+d; 45 Q.push(make_pair(-length[c],c));///优先队列从大到小排，为了从小到大排，我们存入一个负的值 46 } 47 } 48 } 49 return length[n]; 50 } 51 52 int main() 53 { 54 scanf("%lld%lld",&n,&m); 55 for(int i=1;i<=m;i++){ 56 scanf("%lld%lld",&x[i],&y[i]); 57 } 58 ll f=dij(); 59 printf("%lld ",f-1); 60 61 return 0; 62 }