oj.uz

답안 #9772

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
9772 2014-09-28T08:52:30 Z dolpang2 Your life (kriii2_Y) C++14
4 / 4
 204 ms 5144 KB 
#include <iostream>
#include <string>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <utility>

using namespace std;

int dp[100001];
int M, N;
typedef pair<int, int> PAIR;


bool cmp(PAIR x, PAIR y)  {
   if (x.first < y.first){
      return true;
   }
   else if (x.first == y.first) {
      return x.second < y.second;
   }
   else {
      return false;
   }
}
int main(void) {

   int x, y;
   vector<PAIR> edge;
   cin >> N >> M;

   for (int i = 0; i < M; i++) {
      cin >> x >> y;
      edge.push_back(PAIR(x, y));
   }

   sort(edge.begin(), edge.end());

   
   for (vector<PAIR>::iterator itor = edge.begin(); itor != edge.end(); itor++) {
      x = itor->first; y = itor->second;
      if (x != 1 && dp[x] == 0) continue;
      if (dp[y] == 0 || dp[y] > dp[x] + 1) {
         dp[y] = dp[x] + 1;
      }
   }
   

   if (dp[N] == 0) cout << -1 << endl;
   else cout << dp[N] << endl;
   return 0;
}

Subtask #1
1.0 / 1.0

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

Subtask #2
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2068 KB Output is correct
2 Correct 100 ms 3608 KB Output is correct
3 Correct 156 ms 5144 KB Output is correct
4 Correct 132 ms 5144 KB Output is correct
5 Correct 136 ms 5144 KB Output is correct
6 Correct 92 ms 3608 KB Output is correct
7 Correct 96 ms 3608 KB Output is correct
8 Correct 204 ms 5144 KB Output is correct
9 Correct 128 ms 3608 KB Output is correct
10 Correct 196 ms 5144 KB Output is correct