Submission #1988392
Source Code Expand
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
#include<numeric>
#include<limits>
#include<bitset>
#include<functional>
#include<type_traits>
#include<queue>
#include<stack>
#include<array>
#include<random>
namespace lib
{
template<std::uint64_t Mod>struct modnum;
template<class T>constexpr T pow(T base, std::size_t p)
{
if (p == 0)
{
return T(1);
}
else if (p == 1)
{
return base;
}
else if (p == 2)
{
return base * base;
}
else if (p % 2 == 0)
{
return pow(pow(base, p / 2), 2);
}
else
{
return pow(pow(base, p / 2), 2)*base;
}
}
template<std::uint64_t Mod>constexpr auto inverse(modnum<Mod> const&);
template<std::uint64_t Mod>struct modnum
{
static constexpr auto mod = Mod;
std::uint64_t val;
modnum() = default;
constexpr modnum(std::uint64_t v):val(v%Mod)
{
}
constexpr modnum& operator+=(modnum const& v)
{
val += v.val;
val %= mod;
return *this;
}
constexpr modnum& operator-=(modnum const& v)
{
val += mod - v.val;
val %= mod;
return *this;
}
constexpr modnum& operator*=(modnum const& v)
{
val *= v.val;
val %= mod;
return *this;
}
constexpr modnum& operator/=(modnum const& v)
{
return operator*=(inverse(v));
}
};
template<std::uint64_t Mod>constexpr auto operator+(modnum<Mod> lhs, modnum<Mod>const& rhs)
{
return lhs += rhs;
}
template<std::uint64_t Mod>constexpr auto operator-(modnum<Mod> lhs, modnum<Mod>const& rhs)
{
return lhs -= rhs;
}
template<std::uint64_t Mod>constexpr auto operator*(modnum<Mod> lhs, modnum<Mod>const& rhs)
{
return lhs *= rhs;
}
template<std::uint64_t Mod>constexpr auto operator/(modnum<Mod> lhs, modnum<Mod>const& rhs)
{
return lhs /= rhs;
}
template<std::uint64_t Mod>constexpr auto inverse(modnum<Mod>const& base)
{
return pow(base, Mod - 2);
}
template<class T>constexpr auto clamp(T v)
{
return std::max(v, T());
}
template<class T>void sort(T& vec)
{
std::sort(vec.begin(), vec.end());
}
template<class T, class Compare>void sort(T& vec, Compare&& compare)
{
std::sort(vec.begin(), vec.end(), std::forward<Compare>(compare));
}
template<class T>auto lower_bound(std::vector<T>const& vec, T v)
{
return std::distance(vec.begin(), std::lower_bound(vec.begin(), vec.end(), v));
}
template<class T>auto upper_bound(std::vector<T>const& vec, T v)
{
return std::distance(vec.begin(), std::upper_bound(vec.begin(), vec.end(), v));
}
struct scope_exit
{
std::function<void(void)> func;
scope_exit(std::function<void(void)> f):func(f)
{
}
~scope_exit()
{
func();
}
};
template<int val>using int_tag = std::integral_constant<int, val>;
template<class Return, class Argument>struct minimam_searcher
{
Return operator()(std::function<Return(Argument)> func, Argument beg, Argument end)const
{
Return min = std::numeric_limits<Return>::max();
for (; beg != end; ++beg)
{
min = std::min(min, func(beg));
}
return min;
}
};
template<class Return, class Argument>constexpr minimam_searcher<Return, Argument> minimam{};
template<class T>T gcd(T a, T b)
{
if (a > b)
{
return gcd(b, a);
}
if (a == T())
{
return b;
}
return gcd(b%a, a);
}
static constexpr std::int64_t intlog2(std::int64_t x)
{
for (std::int64_t i = 0, j = 2; i < 64; ++i, j <<= 1)
{
if (j > x)
{
return i;
}
}
return 64;
}
struct segtree
{
std::vector<std::int64_t> tree;
std::size_t depth_;
segtree(std::size_t depth):tree(std::size_t(1) << (depth + 1)), depth_(depth)
{
}
void change(std::size_t index, std::int64_t val)
{
change(index, val, 0);
}
std::int64_t get(std::size_t left, std::size_t right)//[left, right]の範囲
{
return get(left, right + 1, 0, 1, 0);
}
void increment(std::size_t index)
{
increment(index, 0);
}
void decrement(std::size_t index)
{
decrement(index, 0);
}
private:
std::int64_t change(std::size_t index, std::int64_t val, std::size_t dep)
{
auto shift = std::size_t(1) << dep;
auto s = std::size_t(1) << (depth_ - dep);
if (dep == depth_)
{
std::swap(tree[shift + index / s - 1], val);
return val;
}
else
{
auto v = change(index, val, dep + 1);
tree[shift + index / s - 1] += val - v;
return v;
}
}
std::int64_t get(std::size_t a, std::size_t b, std::size_t left, std::size_t right, std::size_t dep)
{
auto lshift = left << (depth_ - dep);
auto rshift = right << (depth_ - dep);
if (a <= lshift && rshift <= b)
{
return tree[(std::size_t(1) << dep) + left - 1];
}
else if (rshift <= a || b <= lshift)
{
return 0;
}
else
{
return
get(a, b, left << 1, left + right, dep + 1) +
get(a, b, left + right, right << 1, dep + 1);
}
}
void increment(std::size_t index, std::size_t dep)
{
auto shift = std::size_t(1) << dep;
auto s = std::size_t(1) << (depth_ - dep);
++tree[shift + index / s - 1];
if (dep != depth_)
{
increment(index, dep + 1);
}
}
void decrement(std::size_t index, std::size_t dep)
{
auto shift = std::size_t(1) << dep;
auto s = std::size_t(1) << (depth_ - dep);
--tree[shift + index / s - 1];
if (dep != depth_)
{
decrement(index, dep + 1);
}
}
};
template<class T, int N>class binary_indexed_tree
{
std::array<T, N> ar;
public:
binary_indexed_tree(T val = 0)//全ての要素をvalで初期化する
:ar{}
{
for (int i = 1; i <= N; ++i)
{
ar[i - 1] = (i&-i)*val;
}
}
void add(T val, int index)//index番の要素にvalを足す
{
++index;
for (; index <= N; index += index & -index)
{
ar[index - 1] += val;
}
}
T get(int index)const//0からindex番までの要素の和を返す
{
T ret{};
for (++index; index > 0; index -= index & -index)
{
ret += ar[index - 1];
}
return ret;
}
};
template<class T>using p_queue = std::priority_queue<T, std::vector<T>, std::greater<>>;
template<class T>auto max(std::vector<T>const& vec)
{
return *std::max_element(vec.begin(), vec.end());
}
template<class T>auto min(std::vector<T>const& vec)
{
return *std::min_element(vec.begin(), vec.end());
}
}
namespace std
{
template<std::uint64_t Mod>decltype(auto) operator<<(ostream& ost, lib::modnum<Mod>const& v)
{
return ost << v.val;
}
}
void Main();
int main()
{
std::cin.tie(nullptr);
std::cin.sync_with_stdio(false);
Main();
}
typedef lib::modnum<1000000007> mod_t;
void Main()
{
int N, M;
std::cin >> N >> M;
std::map<int, std::map<int, std::set<int>>> edge;
std::vector<std::set<int>> group(N);
for (int i = 0; i < M; ++i)
{
int p, q, c;
std::cin >> p >> q >> c;
--p; --q; --c;
edge[c][p].emplace(q);
edge[c][q].emplace(p);
for (auto x : edge[c][q])
{
edge[c][p].emplace(x);
edge[c][x].emplace(p);
}
for (auto y : edge[c][p])
{
edge[c][q].emplace(y);
edge[c][y].emplace(q);
}
group[p].emplace(c);
group[q].emplace(c);
}
std::vector<int> cost(N, std::numeric_limits<int>::max());
lib::p_queue<std::pair<int, int>> queue;
queue.emplace(0, 0);
while (queue.size())
{
auto top = queue.top();
queue.pop();
auto cs = top.first;
auto index = top.second;
if (cost[index] <= cs)
{
continue;
}
cost[index] = cs;
for (auto c : group[index])
{
for (auto x : edge[c][index])
{
queue.emplace(cs + 1, x);
}
}
if (index == N - 1)
{
std::cout << cs << std::endl;
return;
}
}
std::cout << -1 << std::endl;
}
Submission Info
Submission Time |
|
Task |
E - Snuke's Subway Trip |
User |
plasmaeffect |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
7947 Byte |
Status |
WA |
Exec Time |
3178 ms |
Memory |
378496 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 600 |
Status |
AC
|
|
Set Name |
Test Cases |
Sample |
|
All |
01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, sample_01.txt, sample_02.txt, sample_03.txt, w1.txt, w10.txt, w11.txt, w12.txt, w13.txt, w14.txt, w15.txt, w16.txt, w17.txt, w18.txt, w2.txt, w3.txt, w4.txt, w5.txt, w6.txt, w7.txt, w8.txt, w9.txt |
Case Name |
Status |
Exec Time |
Memory |
01.txt |
AC |
2 ms |
384 KB |
02.txt |
TLE |
3170 ms |
239872 KB |
03.txt |
AC |
1080 ms |
121456 KB |
04.txt |
AC |
771 ms |
98816 KB |
05.txt |
WA |
1268 ms |
112368 KB |
06.txt |
AC |
421 ms |
51072 KB |
07.txt |
WA |
491 ms |
55680 KB |
08.txt |
AC |
941 ms |
118260 KB |
09.txt |
AC |
457 ms |
58112 KB |
10.txt |
AC |
508 ms |
57980 KB |
11.txt |
TLE |
3177 ms |
365440 KB |
12.txt |
TLE |
3156 ms |
15360 KB |
13.txt |
TLE |
3176 ms |
342656 KB |
14.txt |
TLE |
3177 ms |
361856 KB |
15.txt |
TLE |
3175 ms |
336256 KB |
16.txt |
TLE |
3176 ms |
346624 KB |
17.txt |
TLE |
3177 ms |
367360 KB |
18.txt |
TLE |
3173 ms |
303616 KB |
19.txt |
TLE |
3176 ms |
351488 KB |
20.txt |
TLE |
3177 ms |
365696 KB |
21.txt |
AC |
822 ms |
107768 KB |
22.txt |
TLE |
3178 ms |
378496 KB |
23.txt |
AC |
1267 ms |
119536 KB |
24.txt |
TLE |
3176 ms |
340608 KB |
25.txt |
TLE |
3156 ms |
7808 KB |
26.txt |
TLE |
3173 ms |
303744 KB |
27.txt |
TLE |
3177 ms |
366592 KB |
28.txt |
TLE |
3175 ms |
326272 KB |
29.txt |
TLE |
3176 ms |
345984 KB |
30.txt |
TLE |
3176 ms |
348288 KB |
31.txt |
TLE |
3172 ms |
282240 KB |
32.txt |
TLE |
3175 ms |
340140 KB |
33.txt |
TLE |
3176 ms |
353792 KB |
34.txt |
TLE |
3174 ms |
311808 KB |
35.txt |
TLE |
3156 ms |
7808 KB |
36.txt |
TLE |
3170 ms |
239232 KB |
37.txt |
TLE |
3173 ms |
304384 KB |
38.txt |
TLE |
3173 ms |
304768 KB |
sample_01.txt |
AC |
1 ms |
256 KB |
sample_02.txt |
AC |
1 ms |
256 KB |
sample_03.txt |
AC |
1 ms |
256 KB |
w1.txt |
TLE |
3174 ms |
311424 KB |
w10.txt |
AC |
772 ms |
112000 KB |
w11.txt |
AC |
2186 ms |
3072 KB |
w12.txt |
TLE |
3157 ms |
36224 KB |
w13.txt |
WA |
1163 ms |
58624 KB |
w14.txt |
AC |
1002 ms |
88960 KB |
w15.txt |
AC |
1620 ms |
384 KB |
w16.txt |
TLE |
3155 ms |
8724 KB |
w17.txt |
TLE |
3157 ms |
23936 KB |
w18.txt |
WA |
1459 ms |
46848 KB |
w2.txt |
TLE |
3175 ms |
334336 KB |
w3.txt |
TLE |
3174 ms |
313088 KB |
w4.txt |
TLE |
3172 ms |
281728 KB |
w5.txt |
AC |
962 ms |
120940 KB |
w6.txt |
TLE |
3176 ms |
347008 KB |
w7.txt |
WA |
1153 ms |
112500 KB |
w8.txt |
AC |
1093 ms |
111232 KB |
w9.txt |
AC |
1133 ms |
111104 KB |