ソースコード 拡げる

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;
}
```

提出情報

提出日時 2019-07-03 16:22:33+0900 E - Hopscotch Addict unigiri C++14 (GCC 5.4.1) 500 1251 Byte AC 107 ms 11136 KB

ジャッジ結果

セット名 得点 / 配点 テストケース
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
ケース名 結果 実行時間 メモリ
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