Submission #6223985


Source Code Expand

Copy
#include<bits/stdc++.h>
#define REP(N) for(int i = 0; i < N; i++)
using namespace std;
const int INF = 1e9 + 7;

class State{
  public:
    int step, node, kenkenpa;
    State(int s, int n, int k) { step = s; node = n; kenkenpa = k; }
    bool operator > (const State& s) const { return step > s.step; }
};

int dijkstra(int N, int S, int T, vector< vector<int> >& graph){
  vector< vector<int> > dist(N, vector<int>(3, INF));
  dist[S][0] = 0;
  priority_queue< State, vector<State>, greater<State> > q;
  q.push(State(0, S, 0));
  while(!q.empty()){
    State s = q.top(); q.pop();
    if(dist[s.node][s.kenkenpa] < s.step) continue;
    for(int next : graph[s.node]) {
      int next_kenkenpa = s.kenkenpa == 2 ? 0 : s.kenkenpa + 1;
      if(s.step + 1 >= dist[next][next_kenkenpa]) continue;
      dist[next][next_kenkenpa] = s.step + 1;
      q.push(State(s.step + 1, next, next_kenkenpa));
    }
  }
  return dist[T][0] == INF ? -1 : dist[T][0] / 3;
}

int main(){
  int N, M; cin >>N >>M;
  vector< vector<int> > graph(N, vector<int>());
  REP(M){
    int a, b; cin >>a >>b;
    graph[a - 1].push_back(b - 1);
  }
  int S, T; cin >>S >>T;
  cout <<dijkstra(N, S - 1, T - 1, graph) <<endl;
  return 0;
}

Submission Info

Submission Time
Task E - Hopscotch Addict
User unigiri
Language C++14 (GCC 5.4.1)
Score 500
Code Size 1251 Byte
Status
Exec Time 107 ms
Memory 11136 KB

Test Cases

Set Name Score / Max Score Test Cases
All 500 / 500 cycle_01, cycle_02, cycle_03, killer_01, killer_02, killer_03, killer_04, long_01, long_02, random_dense_01, random_dense_02, random_max_01, random_max_02, random_max_03, random_max_04, random_max_05, random_max_06, sample_01, sample_02, sample_03, sample_04, tournament_01, tournament_02
Sample 0 / 0 sample_01, sample_02, sample_03, sample_04
Case Name Status Exec Time Memory
cycle_01 75 ms 11136 KB
cycle_02 75 ms 11136 KB
cycle_03 75 ms 11136 KB
killer_01 44 ms 896 KB
killer_02 43 ms 896 KB
killer_03 75 ms 10432 KB
killer_04 65 ms 6776 KB
long_01 55 ms 1792 KB
long_02 75 ms 11136 KB
random_dense_01 20 ms 1152 KB
random_dense_02 39 ms 896 KB
random_max_01 86 ms 8192 KB
random_max_02 85 ms 8320 KB
random_max_03 90 ms 6848 KB
random_max_04 89 ms 7552 KB
random_max_05 68 ms 6656 KB
random_max_06 107 ms 10752 KB
sample_01 1 ms 256 KB
sample_02 1 ms 256 KB
sample_03 1 ms 256 KB
sample_04 1 ms 256 KB
tournament_01 43 ms 896 KB
tournament_02 43 ms 896 KB