Submission #3597794

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

int main(){
  int N,M;
  cin>>N>>M;
  std::vector<int> p(M),q(M),c(M);
  for(int i=0;i<M;i++){
    cin>>p[i]>>q[i]>>c[i];
    p[i]--;q[i]--;c[i]--;
  }
  const int INF=1e9;
  std::vector<int> d(N,INF);
  d[0]=0;
  typedef pair<int,int> P;
  std::vector<P> w[N];
  for(int i=0;i<M;i++){
    w[p[i]].push_back(P(q[i],c[i]));
    w[q[i]].push_back(P(p[i],c[i]));
  }
  priority_queue<P> que;
  que.push(P(0,-1));
  while(que.size()){
    P p=que.top();que.pop();
    for(int i=0;i<w[p.first].size();i++){
      if(p.second==w[p.first][i].second){
        if(d[p.first]<d[w[p.first][i].first]){
          d[w[p.first][i].first]=d[p.first];
          que.push(P(w[p.first][i].first,w[p.first][i].second));
        }
      }
      else{
        if(d[p.first]+1<d[w[p.first][i].first]){
          d[w[p.first][i].first]=d[p.first]+1;
          que.push(P(w[p.first][i].first,w[p.first][i].second));
        }
      }
    }
  }
  if(d[N-1]==INF)cout<<-1<<endl;
  else cout<<d[N-1]<<endl;
}

Submission Info

Judge Result