제출 #898215

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
898215		oviyan_gandhi	Olympic Bus (JOI20_ho_t4)	C++17	37 / 100	1033 ms	3932 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];
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 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) << 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: 11 / 11
• Subtask 3: 21 / 21
• Subtask 4: 0 / 63