Submission #6223779


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;
    State(int s, int n) { step = s; node = n; }
    bool operator > (const State& s) const { return step > s.step; }
};

int dijkstra(int N, int S, int T, vector< vector<int> >& graph){
  vector<int> dist(N, INF);
  dist[S] = 0;
  priority_queue< State, vector<State>, greater<State> > q;
  q.push(State(0, S));

  while(!q.empty()){
    State s = q.top(); q.pop();
    if(dist[s.node] < s.step) continue;
    for(int next : graph[s.node]) {
      if(s.step + 1 >= dist[next]) continue;
      dist[next] = s.step + 1;
      q.push(State(s.step + 1, next));
    }
  }

  return dist[T] == INF ? -1 : dist[T];
}

void make_graph(int start, int current, int step, vector< vector<int> >& graph, vector< vector<int> >& orig_graph){
  if(step == 3){
    graph[start].push_back(current);
    return ;
  }
  for(int next : orig_graph[current]) make_graph(start, next, step + 1, graph, orig_graph);
  return ;
}

int main(){
  int N, M; cin >>N >>M;
  vector< vector<int> > orig_graph(N, vector<int>());
  REP(M){
    int a, b; cin >>a >>b;
    orig_graph[a - 1].push_back(b - 1);
  }
  vector< vector<int> > graph(N, vector<int>());
  REP(N){
    make_graph(i, i, 0, graph, orig_graph);
    sort(graph[i].begin(), graph[i].end());
    graph[i].erase(unique(graph[i].begin(), graph[i].end()), graph[i].end());
    //cout <<i <<": "; for(int n : graph[i]) cout <<n <<", "; cout <<endl;
  }
  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 0
Code Size 1683 Byte
Status
Exec Time 2131 ms
Memory 1201612 KB

Judge Result

Set Name All Sample
Score / Max Score 0 / 500 0 / 0
Status
× 16
× 7
× 4
Set Name Test Cases
All 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 sample_01, sample_02, sample_03, sample_04
Case Name Status Exec Time Memory
cycle_01 74 ms 11520 KB
cycle_02 74 ms 11520 KB
cycle_03 74 ms 11520 KB
killer_01 2104 ms 249704 KB
killer_02 2104 ms 247396 KB
killer_03 2131 ms 399744 KB
killer_04 2107 ms 1201612 KB
long_01 294 ms 25984 KB
long_02 75 ms 11520 KB
random_dense_01 70 ms 6784 KB
random_dense_02 2109 ms 184172 KB
random_max_01 90 ms 7680 KB
random_max_02 89 ms 7808 KB
random_max_03 97 ms 7424 KB
random_max_04 100 ms 7552 KB
random_max_05 89 ms 7040 KB
random_max_06 83 ms 11008 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 2104 ms 240088 KB
tournament_02 2104 ms 239448 KB