제출 #564036

#제출 시각아이디문제언어결과실행 시간메모리
564036maomao90Wild Boar (JOI18_wild_boar)C++17
0 / 100
1 ms852 KiB
// Hallelujah, praise the one who set me free // Hallelujah, death has lost its grip on me // You have broken every chain, There's salvation in your name // Jesus Christ, my living hope #include <bits/stdc++.h> using namespace std; #define int ll template <class T> inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;} template <class T> inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;} #define REP(i, s, e) for (int i = s; i < e; i++) #define RREP(i, s, e) for (int i = s; i >= e; i--) typedef long long ll; typedef long double ld; #define FI first #define SE second typedef pair<int, int> ii; typedef pair<ll, ll> pll; typedef tuple<int, int, int> iii; typedef tuple<ll, ll, ll> tll; #define ALL(_a) _a.begin(), _a.end() #define pb push_back typedef vector<int> vi; typedef vector<ll> vll; typedef vector<ii> vii; typedef vector<iii> viii; #ifndef DEBUG #define cerr if (0) cerr #endif const int INF = 1000000005; const ll LINF = 1000000000000000005ll; const int MAXN = 2005; const int MAXL = 100005; int n, m, t, l, e; vi adj[MAXN], radj[MAXN]; int w[MAXN]; int x[MAXL]; ll rd[MAXN][MAXN][5]; int rfi[MAXN][MAXN][5], rse[MAXN][MAXN][5]; ll dp[MAXL][5]; int par[MAXN][2]; ll dist[MAXN][MAXN][2]; int fi[MAXN][MAXN], se[MAXN][MAXN]; priority_queue<tll, vector<tll>, greater<tll>> pq; void dijkstra(int s) { REP (i, 0, e) { dist[s][i][0] = dist[s][i][1] = LINF; fi[s][i] = se[s][i] = -1; par[i][0] = par[i][1] = -1; } dist[s][s][0] = w[s]; pq.push(tll{w[s], s, 0}); while (!pq.empty()) { auto [d, u, tp] = pq.top(); pq.pop(); if (d != dist[s][u][tp]) continue; for (int v : adj[u]) { if (v > n && (v ^ 1) == par[u][tp]) { continue; } ll nd = d + w[v]; if (mnto(dist[s][v][0], nd)) { if (par[v][0] != -1 && par[v][0] != u) { dist[s][v][1] = dist[s][v][0]; par[v][1] = par[v][0]; pq.push(tll{dist[s][v][1], v, 1}); } pq.push(tll{nd, v, 0}); fi[s][v] = fi[s][u] == -1 ? v : fi[s][u]; se[s][v] = u; par[v][0] = u; } else if (mnto(dist[s][v][1], nd)) { pq.push(tll{nd, v, 1}); par[v][1] = u; } } } } main() { #ifndef DEBUG ios::sync_with_stdio(0), cin.tie(0); #endif cin >> n >> m >> t >> l; e = n + 1; if (e & 1) { e++; } REP (i, 0, m) { int a, b, c; cin >> a >> b >> c; w[e] = c; adj[a].pb(e); adj[e].pb(b); radj[a].pb(e++); w[e] = c; adj[b].pb(e); adj[e].pb(a); radj[b].pb(e++); } REP (i, 1, e) { dijkstra(i); } REP (i, 1, n + 1) { REP (j, 1, n + 1) { if (i == j) continue; REP (z, 0, 5) { rd[i][j][z] = LINF; } rd[i][j][0] = dist[i][j][0]; rfi[i][j][0] = fi[i][j]; rse[i][j][0] = se[i][j]; for (int u : radj[i]) { for (int v : radj[j]) { v ^= 1; REP (z, 1, 3) { if ((z == 1 && u == fi[i][j]) || (z == 0 && v == se[i][j])) { continue; } if (mnto(rd[i][j][z], dist[u][v][0])) { rfi[i][j][z] = u; rse[i][j][z] = v; } } } } if (rd[i][j][1] != LINF) { for (int u : radj[i]) { for (int v : radj[j]) { v ^= 1; if (u == fi[i][j] || v == rse[i][j][1]) continue; if (mnto(rd[i][j][3], dist[u][v][0])) { rfi[i][j][3] = u; rse[i][j][3] = v; } } } } if (rd[i][j][2] != LINF) { for (int u : radj[i]) { for (int v : radj[j]) { v ^= 1; if (u == rfi[i][j][2] || v == se[i][j]) continue; if (mnto(rd[i][j][4], dist[u][v][0])) { rfi[i][j][4] = u; rse[i][j][4] = v; } } } } REP (z, 0, 5) { cerr << i << ' ' << j << ' ' << z << ": " << rd[i][j][z] << ' ' << rfi[i][j][z] << ' ' << rse[i][j][z] << '\n'; } cerr << ' ' << fi[i][j] << ' ' << se[i][j] << '\n'; } } x[0] = -1; REP (i, 1, l + 1) { cin >> x[i]; } while (t--) { int p, q; cin >> p >> q; x[p] = q; dp[1][0] = dp[1][1] = dp[1][2] = dp[1][3] = 0; REP (i, 2, l + 1) { int p = x[i - 2], u = x[i - 1], v = x[i]; REP (j, 0, 5) { dp[i][j] = LINF; REP (k, 0, 5) { if (p != -1 && (rse[p][u][k] ^ 1) == rfi[u][v][j]) continue; mnto(dp[i][j], dp[i - 1][k] + rd[u][v][j]); } cerr << i << ' ' << j << ": " << dp[i][j] << '\n'; } } ll ans = min({dp[l][0], dp[l][1], dp[l][2], dp[l][3]}); if (ans >= LINF) { ans = -1; } cout << ans << '\n'; } return 0; }

컴파일 시 표준 에러 (stderr) 메시지

wild_boar.cpp:87:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   87 | main() {
      | ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...