oj.uz

답안 #9165

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
9165 2014-09-28T04:14:32 Z hodduc Your life (kriii2_Y) C++
4 / 4
 84 ms 8232 KB 
// 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.0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 1240 KB Output is correct
2 Correct 0 ms 1240 KB Output is correct
3 Correct 0 ms 1240 KB Output is correct
4 Correct 0 ms 1240 KB Output is correct
5 Correct 0 ms 1240 KB Output is correct
6 Correct 0 ms 1240 KB Output is correct
7 Correct 0 ms 1240 KB Output is correct
8 Correct 0 ms 1240 KB Output is correct
9 Correct 0 ms 1240 KB Output is correct
10 Correct 24 ms 2464 KB Output is correct

Subtask #2
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 4368 KB Output is correct
2 Correct 40 ms 7404 KB Output is correct
3 Correct 64 ms 7536 KB Output is correct
4 Correct 52 ms 7404 KB Output is correct
5 Correct 56 ms 7536 KB Output is correct
6 Correct 32 ms 7404 KB Output is correct
7 Correct 36 ms 7404 KB Output is correct
8 Correct 84 ms 8232 KB Output is correct
9 Correct 48 ms 7404 KB Output is correct
10 Correct 80 ms 7800 KB Output is correct