Submission #898239

#	Time	Username	Problem	Language	Result	Execution time	Memory
898239		oviyan_gandhi	Olympic Bus (JOI20_ho_t4)	C++17	37 / 100	1038 ms	3992 KiB

ho_t4

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
typedef pair<int, int> pii;

#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 dis[MAXN];

int cost(int s, int t, int ri){
    fill(dis, dis+n, INF);
    priority_queue<pii> pq;
    pq.push({0, s});
    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); }

int32_t main(){
    // freopen("sol.in", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    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 fw = min(dist[0][n-1], dist[0][v] + c + dist[u][n-1]),
            bw = min(dist[n-1][0], dist[n-1][v] + c + dist[u][0]);
        if (fw < INF && bw < INF && (fw + bw + d) < ans)
            ans = min(ans, cost(i) + d);
    }
    cout << (ans >= INF ? -1 : ans) << '\n';
    return 0;
}

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