Submission #1093080

#TimeUsernameProblemLanguageResultExecution timeMemory
1093080ortsacOlympic Bus (JOI20_ho_t4)C++17
0 / 100
1 ms348 KiB
#include <bits/stdc++.h> using namespace std; #define int long long int INF = 0x3f3f3f3f3f3f3f3f; struct Edge { int to, c, d; Edge(int x = 0, int y = 0, int z = 0) : to(x), c(y), d(z) {} }; const int MAXN = 205; int gnode[MAXN][MAXN]; int gc[MAXN][MAXN]; int comp[MAXN]; bool vis[MAXN]; int currC = 0; vector<Edge> adj1[MAXN], adj[MAXN]; int n, m; void dfs1(int node, int p) { vis[node] = 1; gnode[p][node] = 1; for (auto u : adj1[node]) { if (!vis[u.to]) dfs1(u.to, p); } } void calcComp(int node) { if (comp[node]) return; comp[node] = currC; for (int i = 1; i <= n; i++) { if (gnode[node][i] && gnode[i][node]) calcComp(i); } } int32_t main() { freopen("in", "r", stdin); cin >> n >> m; for (int i = 1; i <= m; i++) { int a, b, c, d; cin >> a >> b >> c >> d; adj1[a].push_back(Edge(b, c, d)); } for (int i = 1; i <= n; i++) { memset(vis, 0, sizeof vis); dfs1(i, i); } for (int i = 1; i <= n; i++) { if (comp[i]) continue; currC++; calcComp(i); } if (comp[1] == comp[n]) { cout << "0\n"; return 0; } if (!(gnode[1][n] || gnode[n][1])) { cout << "-1\n"; return 0; } for (int i = 1; i <= n; i++) { for (auto u : adj1[i]) { adj[comp[i]].push_back(Edge(comp[u.to], u.c, u.d)); } } int ans = INF; int qtd = 0, mi = INF; for (auto u : adj[comp[1]]) { if (u.to == comp[n]) { qtd++; mi = min(mi, u.d); } } if (qtd >= 2) ans = min(ans, mi); // duas saindo do N qtd = 0, mi = INF; for (auto u : adj[comp[n]]) { if (u.to == comp[1]) { qtd++; mi = min(mi, u.d); } } if (qtd >= 2) ans = min(ans, mi); // componente intermediaria for (int i = 1; i <= currC; i++) { for (int j = 1; j <= currC; j++) { gc[i][j] = INF; } for (auto u : adj[i]) { gc[i][u.to] = min(gc[i][u.to], u.d); } } int s = comp[1], t = comp[n]; if (!gnode[1][n]) swap(s, t); for (int i = 1; i <= currC; i++) { if ((i == s) || (i == t)) continue; if (gc[t][i] != INF) { ans = min(ans, gc[s][i]); } if (gc[i][s] != INF) { ans = min(ans, gc[i][t]); } } // cout resposta if (ans == INF) cout << "-1\n"; else cout << ans << "\n"; }

Compilation message (stderr)

ho_t4.cpp: In function 'int32_t main()':
ho_t4.cpp:39:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |     freopen("in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...