Submission #898144

#	Time	Username	Problem	Language	Result	Execution time	Memory
898144		oviyan_gandhi	Olympic Bus (JOI20_ho_t4)	C++17	26 / 100	1033 ms	6620 KiB

ho_t4

#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];
multiset<pii> adj[MAXN];
int dist[MAXN][MAXN];

int cost(){
    priority_queue<pii> pq;
    pq.push({0, 0});
    vi dis(n, INF);
    dis[0] = 0;
    while (!pq.empty()){
        auto [d, u] = pq.top();
        pq.pop();
        if (dis[u] != d) continue;
        for (auto [v, cd] : adj[u]){
            if (d + cd < dis[v]){
                dis[v] = d + cd;
                pq.push({dis[v], v});
            }
        }
    }
    int ret = dis[n-1];
    fill(dis.begin(), dis.end(), INF);
    dis[n-1] = 0;
    pq.push({0, n-1});
    while (!pq.empty()){
        auto [d, u] = pq.top();
        pq.pop();
        if (dis[u] != d) continue;
        for (auto [v, cd] : adj[u]){
            if (d + cd < dis[v]){
                dis[v] = d + cd;
                pq.push({dis[v], v});
            }
        }
    }
    return ret + dis[0];
}

void REM(int u, int v, int c){ adj[u].erase(adj[u].find({v, c})); }
void ADD(int u, int v, int c){ adj[u].insert({v, c}); }

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;
        adj[i].clear();
    }
    for (int i = 0; i < m; i++){
        Edge &e = edges[i];
        cin >> e.u >> e.v >> e.c >> e.d;
        e.u--, e.v--;
        ADD(e.u, e.v, e.c);
        dist[e.u][e.v] = min(dist[e.u][e.v], e.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){
            REM(u, v, c);
            ADD(v, u, c);
            ans = min(ans, cost() + d);
            REM(v, u, c);
            ADD(u, v, c);
        }
    }
    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;
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 11
• Subtask 3: 21 / 21
• Subtask 4: 0 / 63