제출 #529569

#제출 시각아이디문제언어결과실행 시간메모리
529569abc864197532Robot (JOI21_ho_t4)C++17
0 / 100
3032 ms42720 KiB
#include <bits/stdc++.h> using namespace std; #define lli long long int #define mp make_pair #define pb push_back #define eb emplace_back #define pii pair<int,int> #define X first #define Y second #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() void abc() {cout << endl;} template <typename T, typename ...U> void abc(T i, U ...j) { cout << i << ' ', abc(j...); } template <typename T> void printv(T l, T r) { for (; l != r; ++l) cout << *l << " \n"[l + 1 == r]; } #ifdef Doludu #define test(x...) abc("[" + string(#x) + "]", x) #define owo freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout) #else #define test(x...) void(0) #define owo ios::sync_with_stdio(false), cin.tie(0) #endif const int N = 100000; struct edge { int v, c, p; }; vector <edge> adj[N]; map <int, int> col_num[N]; int main () { owo; int n, m; cin >> n >> m; for (int i = 0, u, v, c, p; i < m; ++i) { cin >> u >> v >> c >> p, --u, --v, --c; adj[u].pb({v, c, p}); adj[v].pb({u, c, p}); col_num[u][c]++, col_num[v][c]++; } map <pair <pii, int>, int> dis; dis[mp(mp(0, 0), -1)] = 0; deque <pair <pii, int>> dq; dq.pb(mp(mp(0, -1), 0)); while (!dq.empty()) { int v, c, del; tie(v, c) = dq.front().X, del = dq.front().Y; dq.pop_front(); int d = dis[mp(mp(v, c), del)]; if (del) col_num[v][c]--; for (edge &e : adj[v]) { if (col_num[v][e.c] == 1) { // no change if (!dis.count(mp(mp(e.v, e.c), 0)) || dis[mp(mp(e.v, e.c), 0)] > d) { dis[mp(mp(e.v, e.c), 0)] = d; dq.push_front(mp(mp(e.v, e.c), 0)); } } // change if (!dis.count(mp(mp(e.v, e.c), 1)) || dis[mp(mp(e.v, e.c), 1)] > d + 1) { dis[mp(mp(e.v, e.c), 1)] = d + 1; dq.push_back(mp(mp(e.v, e.c), 1)); } } if (del) col_num[v][c]++; } int ans = 1 << 30; for (auto A : dis) if (A.X.X.X == n - 1) { ans = min(ans, A.Y); } if (ans == 1 << 30) ans = -1; cout << ans << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...