提出 #6351877

---

ソースコード 拡げる

#include "bits/stdc++.h"
#define in std::cin
#define out std::cout
#define rep(i,N) for(LL i=0;i<N;++i)
typedef long long int LL;
typedef std::pair<LL, LL> P;
struct edge { LL to, cost; };

const LL inf = 1123456789012;
std::vector<std::vector<LL>>dist;
std::vector<std::vector<edge>>G;

void dijkstra(LL s)
{
	std::priority_queue<P, std::vector<P>, std::greater<P>>que;
	dist[s][0] = 0;
	que.push(P(0, s));
	while (!que.empty())
	{
		P p = que.top(); que.pop();
		LL c = p.first, v = p.second;
		if (dist[v][c % 3] < c) continue;
		rep(i, G[v].size())
		{
			edge e = G[v][i];
			if (dist[e.to][(c + 1) % 3] > dist[v][c % 3] + e.cost)
			{
				dist[e.to][(c + 1) % 3] = dist[v][c % 3] + e.cost;
				que.push(P(c + 1, e.to));
			}
		}
	}
}

int main()
{
	LL N, M, S, T;
	in >> N >> M;
	std::vector<LL>u(M), v(M);
	rep(i, M) in >> u[i] >> v[i];
	in >> S >> T;

	dist.resize(N + 1, std::vector<LL>(3, inf));
	G.resize(N + 1);
	rep(i, M) G[u[i]].push_back({ v[i],1 });
	dijkstra(S);

	out << (dist[T][0] != inf ? dist[T][0] / 3 : -1) << std::endl;
}

提出情報

ジャッジ結果