#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <queue>
#include <numeric>
#include <functional>
#include <array>
#include <sstream>
#include <random>
using namespace std;
#define range1(n) for (int __i = 0, __n = int(n); __i < __n; ++__i)
#define range2(i, n) for (int i = 0, __n = int(n); i < __n; ++i)
#define range3(i, a, b) for (int i = int(a), __b = int(b); i < __b; ++i)
#define range4(i, a, b, c) for (int i = int(a), __b = int(b); (c > 0) ? (i < __b) : (i > __b); i += c)
#define GET_MACRO(_1,_2,_3,_4,NAME,...) NAME
#define range(...) GET_MACRO(__VA_ARGS__, range4, range3, range2, range1)(__VA_ARGS__)
#define each2(a, v) for (auto&& a : v)
#define each3(a, b, v) for (auto&& [a, b] : v)
#define each4(a, b, c, v) for (auto&& [a, b, c] : v)
#define each(...) GET_MACRO(__VA_ARGS__, each4, each3, each2, each1)(__VA_ARGS__)
#define iterate(i, a, v) for (auto [it, __end, i] = std::tuple{begin(v), end(v), 0}; it != __end; it++, i++) if (auto&& a = *it; true)
#define len(v) ((int)(v).size())
#define pb push_back
#define all(v) begin(v), end(v)
#define getindex(f,v,...) int(f(all(v),##__VA_ARGS__) - begin(v))
#define endl '\n';
#ifdef DEBUG
#define dprint(a) print(a)
#else
#define dprint(a)
#endif
template <typename U, typename T1, typename T2>
U& operator>>(U& is, std::pair<T1, T2>& p) { return is >> p.first >> p.second; }
template <typename U, typename T, typename enable_if<!is_same<T,string>::value>::type* = nullptr>
U& operator>>(U& is, T& a) { for (auto&& e : a) { is >> e; } return is; }
template <typename U, typename T1, typename T2>
U& operator<<(U& os, const std::pair<T1, T2>& p) { return os << p.first << " " << p.second; }
template <typename U, typename T, typename enable_if<!is_same<T,string>::value>::type* = nullptr>
U& operator<<(U& os, const T& a) { bool f = true; for (auto&& e : a) { if (f) f = false; else os << " "; os << e; } return os; }
template<typename T> void read(T& value) { cin >> value; }
template<typename T, typename... Args> void read(T& value, Args&&... args) { cin >> value; read(forward<Args>(args)...); }
void print() { cout << endl; }
template<typename T, typename... Args> void print(const T& value) { cout << value; print(); }
template<typename T, typename... Args> void print(const T& value, Args&&... args) { cout << value << " "; print(forward<Args>(args)...); }
template <typename T> bool setmin(T& a, const T& b) { if (b < a) {a = b; return true;} return false; }
template <typename T> bool setmax(T& a, const T& b) { if (b > a) {a = b; return true;} return false; }
template <typename T> T gcd(T a, T b) { return b == 0 ? a : gcd(b, a % b); }
template <typename T> int sign(T a) { return a < 0 ? -1 : (a > 0 ? 1 : 0); }
template <typename T> T square(T a) { return a * a; }
template <typename T> void sortunique(T& v) { sort(all(v)); v.erase(unique(all(v)), v.end()); }
template <typename T, typename U=typename T::value_type, typename O=less<U>> vector<int> argsort(const T& v, const O& op = O()) { vector<int> w(len(v)); iota(all(w), 0); sort(all(w), [&](int a, int b) {return v[a] != v[b] ? op(v[a], v[b]) : a < b;}); return w; }
vector<int> invert(const vector<int>& v) { vector<int> w(len(v)); range(i, len(v)) { w[v[i]] = i; } return w; }
template <typename T, typename U=typename T::value_type, typename O=plus<U>> vector<U> prefixes(const T& v, const O& op = O()) { vector<U> sums(len(v)+1); partial_sum(all(v), ++sums.begin(), op); return sums; }
template <typename T, typename U=typename T::value_type> map<U, int> counter(const T& v) { map<U, int> f; for (auto&& e : v) { f[e]++; }; return f; }
template <typename T, typename U=typename T::value_type, typename O=equal_to<U>> vector<pair<U, int> > groupby(const T& v, const O& op = O()) {vector<pair<U, int> > w; for(auto&& a : v) {if (not w.empty() and op(a, w.back().first)) {w.back().second++; } else {w.emplace_back(a, 1); } } return w; }
template <typename Key, typename Value> const Value& getdefault(const map<Key, Value>& m, const Key& key, const Value& default_value) { auto it = m.find(key); if (it == m.end()) {return default_value; } return it->second; }
template <typename Key, typename Value> Value& getdefault(map<Key, Value>& m, const Key& key, Value& default_value) { auto it = m.find(key); if (it == m.end()) {return default_value; } return it->second; }
string OK(bool a) { return a ? "YES" : "NO"; }
string Ok(bool a) { return a ? "Yes" : "No"; }
template<class Fun>
class y_combinator_result {
Fun fun_;
public:
template<class T>
explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}
template<class ...Args>
decltype(auto) operator()(Args &&...args) {
return fun_(std::ref(*this), std::forward<Args>(args)...);
}
};
template<class Fun> decltype(auto) y_combinator(Fun &&fun) { return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun)); }
typedef vector<int> vi;
typedef long long ll;
typedef pair<int,int> pii;
const double pi = acos(-1.0);
constexpr ll inf = (ll)1e18 + 7;
void solve()
{
int n, m;
read(n, m);
vector<vector<array<int,3> > > adj(n);
map<pii, ll> totcost;
range(m) {
int a, b, c, p;
read(a, b, c, p);
a--; b--;
adj[a].pb({b, c, p});
totcost[{a, c}] += p;
adj[b].pb({a, c, p});
totcost[{b, c}] += p;
}
typedef pair<ll, pii> point;
map<pii, ll> dist;
priority_queue<point, vector<point>, greater<point> > pq;
auto getColor = [&](int b, int c) -> ll& {
return dist.insert({{b, c}, inf}).first->second;
};
pq.push({0, {0, 0}});
vi freq(n);
while (not pq.empty()) {
auto [d, cur] = pq.top(); pq.pop();
if (d != dist[cur]) continue;
auto [a, prevc] = cur;
// print(a, prevc, d);
if (a == n-1) {
print(d);
return;
}
if (++freq[a] > 3) continue;
for (auto [b, c, p] : adj[a]) {
if (prevc != c) {
// use c outgoing
ll ndist = d + totcost[{a, c}] - p;
ll &bdist = getColor(b, c);
if (setmin(bdist, ndist)) {
pq.push({ndist, {b, c}});
}
}
{
// change c outgoing
ll ndist = d + p;
ll &bdist = getColor(b, 0);
if (setmin(bdist, ndist)) {
pq.push({ndist, {b, 0}});
}
}
}
}
print(-1);
}
void go()
{
int testn = 1;
// read(testn);
for (int testi = 1; testi <= testn; testi++)
{
solve();
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout << fixed << setprecision(10);
cout << setfill('0');
go();
}
Compilation message
Main.cpp: In function 'void solve()':
Main.cpp:118:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
118 | auto [d, cur] = pq.top(); pq.pop();
| ^
Main.cpp:120:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
120 | auto [a, prevc] = cur;
| ^
Main.cpp:127:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
127 | for (auto [b, c, p] : adj[a]) {
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
364 KB |
Output is correct |
| 4 |
Correct |
1 ms |
364 KB |
Output is correct |
| 5 |
Correct |
1 ms |
364 KB |
Output is correct |
| 6 |
Correct |
1 ms |
364 KB |
Output is correct |
| 7 |
Correct |
3 ms |
492 KB |
Output is correct |
| 8 |
Correct |
1 ms |
364 KB |
Output is correct |
| 9 |
Incorrect |
6 ms |
876 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
457 ms |
15520 KB |
Output is correct |
| 2 |
Correct |
220 ms |
8164 KB |
Output is correct |
| 3 |
Correct |
203 ms |
11380 KB |
Output is correct |
| 4 |
Correct |
104 ms |
8804 KB |
Output is correct |
| 5 |
Incorrect |
1987 ms |
49444 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
364 KB |
Output is correct |
| 4 |
Correct |
1 ms |
364 KB |
Output is correct |
| 5 |
Correct |
1 ms |
364 KB |
Output is correct |
| 6 |
Correct |
1 ms |
364 KB |
Output is correct |
| 7 |
Correct |
3 ms |
492 KB |
Output is correct |
| 8 |
Correct |
1 ms |
364 KB |
Output is correct |
| 9 |
Incorrect |
6 ms |
876 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
