Submission #898205

#TimeUsernameProblemLanguageResultExecution timeMemory
898205oviyan_gandhiOlympic Bus (JOI20_ho_t4)C++17
37 / 100
1042 ms5052 KiB
#define ONLINE_JUDGE #include <bits/stdc++.h> using namespace std; #ifdef ONLINE_JUDGE #define endl '\n' #endif #define int long long #define all(x) x.begin(), x.end() typedef vector<int> vi; typedef vector<vector<int>> vvi; typedef vector<bool> vb; typedef vector<vector<bool>> vvb; typedef pair<int, int> pii; typedef map<int, int> mii; typedef map<int, vector<int>> mivi; const int mod = 1000000007; // 10^9 + 7 const int INF = 1e17; #define MAXN 200 #define MAXM 50000 struct Edge { int u, v, c, d; }; int n, m; Edge edges[MAXM]; list<int> adj[MAXN]; int dist[MAXN][MAXN]; int cost(int s, int t, int ri){ priority_queue<pii> pq; pq.push({0, s}); vi dis(n, INF); dis[s] = 0; while (!pq.empty()){ auto [d, u] = pq.top(); pq.pop(); if (dis[u] != d) continue; if (ri != -1 && edges[ri].v == u){ int v = edges[ri].u, cd = edges[ri].c; if (d + cd < dis[v]){ dis[v] = d + cd; pq.push({dis[v], v}); } } for (int i : adj[u]){ if (i == ri) continue; int v = edges[i].v, cd = edges[i].c; if (d + cd < dis[v]){ dis[v] = d + cd; pq.push({dis[v], v}); } } } return dis[t]; } int cost(int ri = -1){ return cost(0, n-1, ri) + cost(n-1, 0, ri); } void solve(){ cin >> n >> m; for (int i = 0; i < n; i++){ for (int j = 0; j < n; j++) dist[i][j] = INF; dist[i][i] = 0; } for (int i = 0; i < m; i++){ auto &[u, v, c, d] = edges[i]; cin >> u >> v >> c >> d; u--, v--; adj[u].push_back(i); dist[u][v] = min(dist[u][v], c); } for (int k = 0; k < n; k++) for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]); int ans = cost(); for (int i = 0; i < m; i++){ auto [u, v, c, d] = edges[i]; int p = min(dist[0][n-1], dist[0][v] + c + dist[u][n-1]) + min(dist[n-1][0], dist[n-1][v] + c + dist[u][0]) + d; if (p < ans) ans = min(ans, cost(i) + d); } cout << (ans >= INF ? -1 : ans) << endl; } int32_t main(){ #ifndef ONLINE_JUDGE auto begin = chrono::high_resolution_clock::now(); freopen("sol.in", "r", stdin); #endif ios_base::sync_with_stdio(false); cin.tie(NULL); int T = 1;// cin >> T; for (int i = 1; i <= T; i++){ #ifndef ONLINE_JUDGE if (T != 1) cout << "Test Case #" << i << endl; #endif solve(); } #ifndef ONLINE_JUDGE auto elapsed = chrono::duration_cast<chrono::nanoseconds>(chrono::high_resolution_clock::now() - begin); cout << "Time Taken : " << (elapsed.count() * 1e-9) << " seconds" << endl; #endif return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...