Submission #9165

#	Time	Username	Problem	Language	Result	Execution time	Memory
9165		hodduc	Your life (kriii2_Y)	C++98	4 / 4	84 ms	8232 KiB

Y

// Implementation of Dijkstra's algorithm using adjacency lists
// and priority queue for efficiency.
//
// Running time: O(|E| log |V|)

#include <queue>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <functional>

using namespace std;
const int INF = 2000000000;
typedef pair<int,int> PII;

int main(){
  
  int N, s, t, M;
  int a, b;

  scanf("%d %d", &N, &M);
  s = 0; t = N-1;
  
  vector<vector<PII> > edges(N);
  for (int i = 0; i < M; i++){
	  scanf("%d %d", &a, &b);
	  edges[a-1].push_back(make_pair(1, b-1));
  }
  
  // use priority queue in which top element has the "smallest" priority
  priority_queue<PII, vector<PII>, greater<PII> > Q;
  vector<int> dist(N, INF), dad(N, -1);
  Q.push (make_pair (0, s));
  dist[s] = 0;
  while (!Q.empty()){
    PII p = Q.top();
    if (p.second == t) break;
    Q.pop();
    
    int here = p.second;
    for (vector<PII>::iterator it=edges[here].begin(); it!=edges[here].end(); it++){
      if (dist[here] + it->first < dist[it->second]){
        dist[it->second] = dist[here] + it->first;
        dad[it->second] = here;
        Q.push (make_pair (dist[it->second], it->second));
      }
    }
  }
  
  if(dist[t] == INF) printf("-1\n");
  else printf ("%d\n", dist[t]);
  return 0;
}

• Subtask 1: 1 / 1
• Subtask 2: 3 / 3