#line 1 "a.cpp" // https://qandori.github.io/cp-library/ // #include #include using namespace std; using std::cin, std::cout, std::cerr; #define vec vector typedef long double ld; #if LONG_MAX == 2147483647L #undef long #define long long long #endif #define uint unsigned int #define ulong unsigned long #define overload3(a, b, c, name, ...) name #define rep3(i, a, b) for (int i = (a); i < (b); i++) #define rep2(i, n) rep3(i, 0, n) #define rep1(n) rep2(__i__, n) #define rep(...) overload3(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__) #define per3(i, a, b) for (int i = (b) - 1; i >= (a); i--) #define per2(i, n) per3(i, 0, n) #define per1(n) per2(__i__, n) #define per(...) overload3(__VA_ARGS__, per3, per2, per1)(__VA_ARGS__) #define CP_ALL_SELECT(first, ...) first #define CP_ALL_RANGE(a) std::begin(a), std::end(a) #define all(...) CP_ALL_SELECT(__VA_OPT__(CP_ALL_RANGE, ) all)(__VA_ARGS__) #define UNIQUE(a) sort(all(a)), a.erase(unique(all(a)), a.end()), a.shrink_to_fit() #define sz(a) static_cast(a.size()) #ifndef DEBUG #define cerr \ if (false) cerr #undef endl #define endl '\n' #endif inline auto operator^=(vector::reference a, bool b) noexcept { if (b) a.flip(); return a; } inline auto operator&=(vector::reference a, bool b) noexcept { if (!b) a = false; return a; } inline auto operator|=(vector::reference a, bool b) noexcept { if (b) a = true; return a; } inline ostream &operator<<(ostream &os, __int128_t value) { ostream::sentry s(os); if (s) { __uint128_t tmp = value; if (value < 0) tmp = -tmp; char buffer[128]; char *d = std::end(buffer); do { --d; *d = "0123456789"[tmp % 10]; tmp /= 10; } while (tmp != 0); if (value < 0) --d, *d = '-'; const int len = std::end(buffer) - d; if (os.rdbuf()->sputn(d, len) != len) os.setstate(std::ios_base::badbit); } return os; } template ostream &operator<<(ostream &os, pair a) { return os << a.first << ' ' << a.second; }; template ostream &operator<<(ostream &os, vector a) { const int n = a.size(); rep(i, n) { os << a[i]; if (i + 1 != n) os << " "; } return os; } template istream &operator>>(istream &is, pair &a) { return is >> a.first >> a.second; } template ostream &operator<<(ostream &os, array a) { rep(i, n) { os << a[i]; if (i + 1 != n) os << " "; } return os; } template istream &operator>>(istream &is, vector &a) { for (T &i : a) is >> i; return is; } template bool chmin(T &x, S y) { if ((T)y < x) { x = (T)y; return true; } return false; } template bool chmax(T &x, S y) { if (x < (T)y) { x = (T)y; return true; } return false; } template void operator++(vector &a) { for (T &i : a) ++i; } template void operator--(vector &a) { for (T &i : a) --i; } template void operator++(vector &a, int) { for (T &i : a) i++; } template void operator--(vector &a, int) { for (T &i : a) i--; } void init(), solve(); int main() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(20); cerr << fixed << setprecision(20); init(); int t = 1; // cin >> t; while (t--) solve(); } // #define COMB_MAX 1e6 // #include "lib/math/comb.hpp" // #include "lib/fps/fps.hpp" // #include "lib/math/mint.hpp" void init() {} #line 1 "lib/graph/warshall_floyd.hpp" #line 1 "lib/components/warshall_floyd_kernel.hpp" #line 1 "lib/components/aligned_allocator.hpp" #line 7 "lib/components/aligned_allocator.hpp" template struct AlignedAllocator { static_assert(Alignment >= alignof(T) && !(Alignment & (Alignment - 1))); using value_type = T; template struct rebind { using other = AlignedAllocator; }; AlignedAllocator() = default; template AlignedAllocator(const AlignedAllocator &) {} T *allocate(std::size_t n) { if (n > std::numeric_limits::max() / sizeof(T)) throw std::bad_array_new_length(); return static_cast(::operator new(n * sizeof(T), std::align_val_t(Alignment))); } void deallocate(T *p, std::size_t) { ::operator delete(p, std::align_val_t(Alignment)); } template bool operator==(const AlignedAllocator &) const { return true; } }; #line 10 "lib/components/warshall_floyd_kernel.hpp" #include #line 12 "lib/components/warshall_floyd_kernel.hpp" #if (defined(__x86_64__) || defined(__i386__)) && (defined(__GNUC__) || defined(__clang__)) #include #endif #if defined(__GNUC__) && !defined(__clang__) #pragma GCC push_options #pragma GCC optimize("O3") #endif #if !defined(WARSHALL_FLOYD_DISABLE_AVX512) && !defined(WARSHALL_FLOYD_DISABLE_SIMD) && (defined(__x86_64__) || defined(__i386__)) #if defined(__GNUC__) && !defined(__clang__) _Pragma("GCC push_options") _Pragma("GCC target(\"no-avx512f,avx512f\")") #ifdef __AVX512F__ #define WARSHALL_FLOYD_DETAIL_AVX512 #endif _Pragma("GCC pop_options") #elif defined(__clang__) #define WARSHALL_FLOYD_DETAIL_AVX512 #endif #endif namespace warshall_floyd_detail { template using Storage = std::vector>; template struct Unsigned { using type = std::make_unsigned_t; }; template<> struct Unsigned<__int128_t> { using type = __uint128_t; }; inline int backend() { #if (defined(__x86_64__) || defined(__i386__)) && (defined(__GNUC__) || defined(__clang__)) && !defined(WARSHALL_FLOYD_DISABLE_SIMD) #ifdef WARSHALL_FLOYD_DETAIL_AVX512 if (__builtin_cpu_supports("avx512f")) return 2; #endif if (__builtin_cpu_supports("avx2")) return 1; #endif return 0; } template bool scalar(T* out, const T* a, const T* b, T inf) { for (int k = 0; k < B; ++k) { if constexpr (Diagonal && Negative) if (out[k * B + k] < 0) return false; for (int i = 0; i < B; ++i) { T x = a[i * B + k]; if (x == inf) continue; for (int j = 0; j < B; ++j) { if constexpr (Negative) { if (b[k * B + j] != inf) out[i * B + j] = std::min(out[i * B + j], T(x + b[k * B + j])); } else { using U = typename Unsigned::type; out[i * B + j] = T(std::min(U(out[i * B + j]), U(x) + U(b[k * B + j]))); } } } } return true; } #if (defined(__x86_64__) || defined(__i386__)) && (defined(__GNUC__) || defined(__clang__)) #ifdef WARSHALL_FLOYD_DETAIL_AVX512 template __attribute__((target("avx512f"))) bool simple512(T* out, const T* a, const T* b, T inf) { constexpr int lanes = 64 / sizeof(T); [[maybe_unused]] __m512i infinity; if constexpr (sizeof(T) == 4) infinity = _mm512_set1_epi32(inf); else infinity = _mm512_set1_epi64(inf); for (int k = 0; k < B; ++k) { if constexpr (Diagonal && Negative) if (out[k * B + k] < 0) return false; for (int i = 0; i < B; ++i) { T x = a[i * B + k]; if constexpr (Negative) if (x == inf) continue; __m512i alpha; if constexpr (sizeof(T) == 4) alpha = _mm512_set1_epi32(x); else alpha = _mm512_set1_epi64(x); for (int j = 0; j < B; j += lanes) { auto value = _mm512_loadu_si512(out + i * B + j); auto beta = _mm512_loadu_si512(b + k * B + j); [[maybe_unused]] __mmask16 valid = 0; if constexpr (Negative && sizeof(T) == 4) valid = _mm512_cmpneq_epi32_mask(beta, infinity); if constexpr (Negative && sizeof(T) == 8) valid = _mm512_cmpneq_epi64_mask(beta, infinity); if constexpr (sizeof(T) == 4) { auto sum = _mm512_add_epi32(alpha, beta); if constexpr (Negative) value = _mm512_mask_min_epi32(value, valid, value, sum); else value = _mm512_min_epu32(value, sum); } else { auto sum = _mm512_add_epi64(alpha, beta); if constexpr (Negative) value = _mm512_mask_min_epi64(value, __mmask8(valid), value, sum); else value = _mm512_min_epu64(value, sum); } _mm512_storeu_si512(out + i * B + j, value); } } } return true; } template __attribute__((target("avx512f"))) void product512(T* out, const T* a, const T* b, T inf) { constexpr int lanes = 64 / sizeof(T), rows = 4, columns = 2; [[maybe_unused]] __m512i infinity; if constexpr (sizeof(T) == 4) infinity = _mm512_set1_epi32(inf); else infinity = _mm512_set1_epi64(inf); for (int i = 0; i < B; i += rows) for (int j = 0; j < B; j += lanes * columns) { __m512i value[rows][columns]; for (int r = 0; r < rows; ++r) for (int q = 0; q < columns; ++q) value[r][q] = _mm512_loadu_si512(out + (i + r) * B + j + q * lanes); for (int k = 0; k < B; ++k) { __m512i beta[columns]; [[maybe_unused]] __mmask16 valid[columns]{}; for (int q = 0; q < columns; ++q) { beta[q] = _mm512_loadu_si512(b + k * B + j + q * lanes); __mmask16 mask = 0; if constexpr (Negative && sizeof(T) == 4) mask = _mm512_cmpneq_epi32_mask(beta[q], infinity); if constexpr (Negative && sizeof(T) == 8) mask = _mm512_cmpneq_epi64_mask(beta[q], infinity); valid[q] = mask; } for (int r = 0; r < rows; ++r) { T x = a[(i + r) * B + k]; if constexpr (Negative) if (x == inf) continue; __m512i alpha; if constexpr (sizeof(T) == 4) alpha = _mm512_set1_epi32(x); else alpha = _mm512_set1_epi64(x); for (int q = 0; q < columns; ++q) { if constexpr (sizeof(T) == 4) { auto sum = _mm512_add_epi32(alpha, beta[q]); if constexpr (Negative) value[r][q] = _mm512_mask_min_epi32(value[r][q], valid[q], value[r][q], sum); else value[r][q] = _mm512_min_epu32(value[r][q], sum); } else { auto sum = _mm512_add_epi64(alpha, beta[q]); if constexpr (Negative) value[r][q] = _mm512_mask_min_epi64(value[r][q], __mmask8(valid[q]), value[r][q], sum); else value[r][q] = _mm512_min_epu64(value[r][q], sum); } } } } for (int r = 0; r < rows; ++r) for (int q = 0; q < columns; ++q) _mm512_storeu_si512(out + (i + r) * B + j + q * lanes, value[r][q]); } } #endif template __attribute__((target("avx2"))) bool simple256(T* out, const T* a, const T* b, T inf) { constexpr int lanes = 32 / sizeof(T); [[maybe_unused]] __m256i infinity; if constexpr (sizeof(T) == 4) infinity = _mm256_set1_epi32(inf); else infinity = _mm256_set1_epi64x(inf); for (int k = 0; k < B; ++k) { if constexpr (Diagonal && Negative) if (out[k * B + k] < 0) return false; for (int i = 0; i < B; ++i) { T x = a[i * B + k]; if constexpr (Negative) if (x == inf) continue; __m256i alpha; if constexpr (sizeof(T) == 4) alpha = _mm256_set1_epi32(x); else alpha = _mm256_set1_epi64x(x); for (int j = 0; j < B; j += lanes) { auto value = _mm256_loadu_si256(reinterpret_cast(out + i * B + j)); auto beta = _mm256_loadu_si256(reinterpret_cast(b + k * B + j)); [[maybe_unused]] __m256i valid = _mm256_setzero_si256(); if constexpr (Negative && sizeof(T) == 4) valid = _mm256_cmpeq_epi32(beta, infinity); if constexpr (Negative && sizeof(T) == 8) valid = _mm256_cmpeq_epi64(beta, infinity); if constexpr (sizeof(T) == 4) { auto sum = _mm256_add_epi32(alpha, beta); if constexpr (Negative) value = _mm256_min_epi32(value, _mm256_blendv_epi8(sum, infinity, valid)); else value = _mm256_min_epu32(value, sum); } else { auto sum = _mm256_add_epi64(alpha, beta); if constexpr (Negative) { sum = _mm256_blendv_epi8(sum, infinity, valid); value = _mm256_blendv_epi8(value, sum, _mm256_cmpgt_epi64(value, sum)); } else { auto choose = _mm256_andnot_si256(_mm256_cmpgt_epi64(_mm256_setzero_si256(), sum), _mm256_cmpgt_epi64(value, sum)); value = _mm256_blendv_epi8(value, sum, choose); } } _mm256_storeu_si256(reinterpret_cast<__m256i*>(out + i * B + j), value); } } } return true; } template __attribute__((target("avx2"))) void product256(T* out, const T* a, const T* b, T inf) { constexpr int lanes = 32 / sizeof(T), rows = 4, columns = 2; [[maybe_unused]] __m256i infinity; if constexpr (sizeof(T) == 4) infinity = _mm256_set1_epi32(inf); else infinity = _mm256_set1_epi64x(inf); for (int i = 0; i < B; i += rows) for (int j = 0; j < B; j += lanes * columns) { __m256i value[rows][columns]; for (int r = 0; r < rows; ++r) for (int q = 0; q < columns; ++q) value[r][q] = _mm256_loadu_si256(reinterpret_cast(out + (i + r) * B + j + q * lanes)); for (int k = 0; k < B; ++k) { __m256i beta[columns]; [[maybe_unused]] __m256i valid[columns]{}; for (int q = 0; q < columns; ++q) { beta[q] = _mm256_loadu_si256(reinterpret_cast(b + k * B + j + q * lanes)); __m256i mask = _mm256_setzero_si256(); if constexpr (Negative && sizeof(T) == 4) mask = _mm256_cmpeq_epi32(beta[q], infinity); if constexpr (Negative && sizeof(T) == 8) mask = _mm256_cmpeq_epi64(beta[q], infinity); valid[q] = mask; } for (int r = 0; r < rows; ++r) { T x = a[(i + r) * B + k]; if constexpr (Negative) if (x == inf) continue; __m256i alpha; if constexpr (sizeof(T) == 4) alpha = _mm256_set1_epi32(x); else alpha = _mm256_set1_epi64x(x); for (int q = 0; q < columns; ++q) { if constexpr (sizeof(T) == 4) { auto sum = _mm256_add_epi32(alpha, beta[q]); if constexpr (Negative) value[r][q] = _mm256_min_epi32(value[r][q], _mm256_blendv_epi8(sum, infinity, valid[q])); else value[r][q] = _mm256_min_epu32(value[r][q], sum); } else { auto sum = _mm256_add_epi64(alpha, beta[q]); if constexpr (Negative) { sum = _mm256_blendv_epi8(sum, infinity, valid[q]); value[r][q] = _mm256_blendv_epi8(value[r][q], sum, _mm256_cmpgt_epi64(value[r][q], sum)); } else { auto choose = _mm256_andnot_si256(_mm256_cmpgt_epi64(_mm256_setzero_si256(), sum), _mm256_cmpgt_epi64(value[r][q], sum)); value[r][q] = _mm256_blendv_epi8(value[r][q], sum, choose); } } } } } for (int r = 0; r < rows; ++r) for (int q = 0; q < columns; ++q) _mm256_storeu_si256(reinterpret_cast<__m256i*>(out + (i + r) * B + j + q * lanes), value[r][q]); } } #endif template struct Kernel { static bool close(T* out, T inf) { #if (defined(__x86_64__) || defined(__i386__)) && (defined(__GNUC__) || defined(__clang__)) #ifdef WARSHALL_FLOYD_DETAIL_AVX512 if constexpr (Backend == 2) return simple512(out, out, out, inf); #endif if constexpr (Backend == 1) return simple256(out, out, out, inf); #endif return scalar(out, out, out, inf); } static void edge(T* out, const T* a, const T* b, T inf) { #if (defined(__x86_64__) || defined(__i386__)) && (defined(__GNUC__) || defined(__clang__)) #ifdef WARSHALL_FLOYD_DETAIL_AVX512 if constexpr (Backend == 2) { simple512(out, a, b, inf); return; } #endif if constexpr (Backend == 1) { simple256(out, a, b, inf); return; } #endif scalar(out, a, b, inf); } static void product(T* out, const T* a, const T* b, T inf) { #if (defined(__x86_64__) || defined(__i386__)) && (defined(__GNUC__) || defined(__clang__)) #ifdef WARSHALL_FLOYD_DETAIL_AVX512 if constexpr (Backend == 2) { product512(out, a, b, inf); return; } #endif if constexpr (Backend == 1) { product256(out, a, b, inf); return; } #endif scalar(out, a, b, inf); } }; template bool solve(T* data, int blocks, T inf) { using K = Kernel; auto tile = [&](int i, int j) { return data + (std::size_t(i) * blocks + j) * B * B; }; auto product = [&](int row, int col, int pivot, int rows, int cols, int inner) { for (int k = pivot; k < pivot + inner; ++k) for (int i = row; i < row + rows; ++i) for (int j = col; j < col + cols; ++j) K::product(tile(i, j), tile(i, k), tile(k, j), inf); }; constexpr int macro = 16; for (int base = 0; base < blocks; base += macro) { int size = std::min(macro, blocks - base); for (int k = base; k < base + size; ++k) { if (!K::close(tile(k, k), inf)) return false; for (int j = base; j < base + size; ++j) if (j != k) K::edge(tile(k, j), tile(k, k), tile(k, j), inf); for (int i = base; i < base + size; ++i) if (i != k) K::edge(tile(i, k), tile(i, k), tile(k, k), inf); for (int i = base; i < base + size; ++i) if (i != k) for (int j = base; j < base + size; ++j) if (j != k) K::product(tile(i, j), tile(i, k), tile(k, j), inf); } for (int j = 0; j < blocks; j += macro) if (j != base) product(base, j, base, size, std::min(macro, blocks - j), size); for (int i = 0; i < blocks; i += macro) if (i != base) product(i, base, base, std::min(macro, blocks - i), size, size); for (int i = 0; i < blocks; i += macro) if (i != base) for (int j = 0; j < blocks; j += macro) if (j != base) product(i, j, base, std::min(macro, blocks - i), std::min(macro, blocks - j), size); } return true; } template bool run(T* data, int blocks, T inf, int selected = backend()) { if constexpr (sizeof(T) <= 8) { if (selected == 2) return solve(data, blocks, inf); if (selected == 1) return solve(data, blocks, inf); } return solve(data, blocks, inf); } } #if defined(__GNUC__) && !defined(__clang__) #pragma GCC pop_options #endif #undef WARSHALL_FLOYD_DETAIL_AVX512 #line 6 "lib/graph/warshall_floyd.hpp" template class WarshallFloyd { static_assert(std::is_integral_v && std::is_signed_v && (sizeof(T) == 4 || sizeof(T) == 8)); static constexpr int block = 32; int n_ = 0, blocks_ = 0; T infinity_ = std::numeric_limits::max(); warshall_floyd_detail::Storage data_; static int checked_size(std::size_t n) { if (n > std::size_t(std::numeric_limits::max())) throw std::length_error("Warshall-Floyd size"); return int(n); } std::size_t index(int i, int j) const { return (std::size_t(i / block) * blocks_ + j / block) * block * block + i % block * block + j % block; } template bool run_as(bool negative) { const U inf = std::numeric_limits::max(); warshall_floyd_detail::Storage work(data_.size()); for (std::size_t i = 0; i < data_.size(); ++i) work[i] = data_[i] == infinity_ ? inf : U(data_[i]); bool success = negative ? warshall_floyd_detail::run(work.data(), blocks_, inf) : warshall_floyd_detail::run(work.data(), blocks_, inf); if (success) for (U value : work) if (value != inf && (__int128_t(value) < std::numeric_limits::lowest() || __int128_t(value) >= infinity_)) throw std::overflow_error("Warshall-Floyd distance"); for (std::size_t i = 0; i < data_.size(); ++i) { if (work[i] == inf) data_[i] = infinity_; else data_[i] = T(std::clamp(__int128_t(work[i]), __int128_t(std::numeric_limits::lowest()), __int128_t(infinity_) - 1)); } return success; } public: using value_type = T; explicit WarshallFloyd(int n = 0, T inf = std::numeric_limits::max()) : n_(n), infinity_(inf) { if (n < 0 || inf <= 0) throw std::invalid_argument("Warshall-Floyd shape or infinity"); blocks_ = n / block + (n % block != 0); std::size_t padded = std::size_t(blocks_) * block; data_.assign(padded * padded, infinity_); for (std::size_t i = 0; i < padded; ++i) data_[index(int(i), int(i))] = 0; } explicit WarshallFloyd(const std::vector>& distance, T inf = std::numeric_limits::max()) : WarshallFloyd(checked_size(distance.size()), inf) { for (int i = 0; i < n_; ++i) { if (distance[i].size() != std::size_t(n_)) throw std::invalid_argument("Warshall-Floyd matrix"); for (int j = 0; j < n_; ++j) { if (distance[i][j] == infinity_) continue; add_edge(i, j, distance[i][j]); } } } int size() const { return n_; } T infinity() const { return infinity_; } T operator()(int i, int j) const { assert(0 <= i && i < n_ && 0 <= j && j < n_); return data_[index(i, j)]; } void add_edge(int from, int to, T weight) { assert(0 <= from && from < n_ && 0 <= to && to < n_); if (weight >= infinity_) throw std::invalid_argument("Warshall-Floyd edge"); auto& value = data_[index(from, to)]; value = std::min(value, weight); } bool solve() { __int128_t maximum = 0; std::size_t finite = 0; bool negative = false; for (T value : data_) if (value != infinity_) { ++finite; __int128_t x = value; negative |= x < 0; maximum = std::max(maximum, x < 0 ? -x : x); } __int128_t bound = 2 * (__int128_t(n_) + 1) * maximum; bool complete = finite == std::size_t(n_) * n_ + std::size_t(blocks_) * block - n_; if constexpr (sizeof(T) == 8) { #ifndef WARSHALL_FLOYD_DISABLE_NARROWING __int128_t limit = std::min(__int128_t(infinity_), __int128_t(std::numeric_limits::max())); if (negative ? bound < limit : maximum < limit && (complete || (__int128_t(n_) - 1) * maximum < limit)) return run_as(negative); #endif } if (negative ? bound >= infinity_ : !complete && (__int128_t(n_) - 1) * maximum >= infinity_) { if constexpr (sizeof(T) == 4) { if (bound < std::numeric_limits::max()) return run_as(negative); } return run_as<__int128_t>(negative); } return negative ? warshall_floyd_detail::run(data_.data(), blocks_, infinity_) : warshall_floyd_detail::run(data_.data(), blocks_, infinity_); } std::vector> distances() const { std::vector> result(n_, std::vector(n_)); for (int i = 0; i < n_; ++i) for (int j = 0; j < n_; ++j) result[i][j] = data_[index(i, j)]; return result; } }; template bool warshall_floyd(std::vector>& distance, T inf = std::numeric_limits::max()) { WarshallFloyd work(distance, inf); bool success = work.solve(); distance = work.distances(); return success; } #line 143 "a.cpp" void solve() { int n, m; cin >> n >> m; vec p(n); cin >> p; WarshallFloyd<> g(n); while (m--) { int u, v; long t; cin >> u >> v >> t; g.add_edge(u - 1, v - 1, t); } g.solve(); long ans = LONG_MAX, cnt = 0; rep(i, n) rep(j, n) { if (i == j || g(i, j) == g.infinity()) continue; const long cost = g(i, j) + p[i] + p[j]; if (chmin(ans, cost)) cnt = 0; if (cost == ans) cnt++; } cout << ans << ' ' << cnt << '\n'; }