Contest Duration: ~ (local time) (100 minutes) Back to Home

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 2019-07-03 16:04:23+0900 E - Hopscotch Addict unigiri C++14 (GCC 5.4.1) 0 1683 Byte TLE 2131 ms 1201612 KB

#### Judge Result

Set Name All Sample
Score / Max Score 0 / 500 0 / 0
Status
 AC × 16 TLE × 7
 AC × 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