oj.uz

답안 #958467

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
958467 2024-04-05T20:35:10 Z BhavayGoyal Olympic Bus (JOI20_ho_t4) C++14
5 / 100
 82 ms 7672 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define vi vector<int>
#define vii vector<vector<int>>
#define pii pair<int, int>
#define pb push_back
#define f first
#define s second
#define endl "\n"

const int linf = 1e15;

// -------------------------------------------------- Main Code --------------------------------------------------

const int N = 201, M = 50001;
int n, m;
set<pii> g[N];
vii edges;
map<pair<int, int>, bool> isShort;
map<pii, pii> edge;

pair<vi, vi> dijkstra(int source) {
    priority_queue<pii, vector<pii>, greater<>> q;
    vi vis(n+1, 0), dis(n+1, linf), par(n+1);
    q.push({0, source});
    dis[source] = 0;
    while (!q.empty()) {
        pii f = q.top(); q.pop();
        int src = f.s;
        if (vis[src]) continue;
        vis[src] = true;

        for (auto child : g[src]) {
            int ch = child.f, wt = child.s;
            if (dis[ch] > dis[src] + wt) {
                par[ch] = src;
                dis[ch] = dis[src] + wt;
                q.push({dis[ch], ch});
            }
        }
    }
    return {dis, par};
}

void sol() {
    cin >> n >> m;
    vii dist(n+1, vi(n+1, linf));
    for (int i = 1; i <= n; i++) dist[i][i] = 0;
    
    for (int i = 1; i <= m; i++) {
        int a, b, c, d; cin >> a >> b >> c >> d;
        dist[a][b] = min(dist[a][b], c);
        g[a].insert({b, c});
        edges.pb({a, b, c, d});
    }

    pair<vi, vi> x = dijkstra(1); vi dis = x.f, par = x.s;
    int c = n;
    while (par[c]) {
        pii temp = edge[{par[c], c}];
        isShort[{par[c], c}] = true;
        c = par[c];
    }

    x = dijkstra(n); dis = x.f, par = x.s;
    c = 1;
    while (par[c]) {
        pii temp = edge[{par[c], c}];
        isShort[{par[c], c}] = true;
        c = par[c];
    }

    for (int k = 1; k <= n; ++k) {
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }

    int ans = min(linf, dist[1][n] + dist[n][1]);

    for (auto i : edges) {
        int a = i[0], b = i[1], c = i[2], d = i[3];
        if (isShort[{a, b}]) {
            int a = i[0], b = i[1], c = i[2], d = i[3];
            g[a].erase({b, c});
            g[b].insert({a, c});
            pair<vi, vi> x = dijkstra(1);
            pair<vi, vi> y = dijkstra(n);
            ans = min(ans, x.f[n] + y.f[1] + d);
            g[b].erase({a, c});
            g[a].insert({b, c});
        }
        else {
            int new1n = dist[1][b] + c + dist[a][n];
            int newn1 = dist[n][b] + c + dist[a][1];
            ans = min(ans, dist[1][n] + newn1 + d);
            ans = min(ans, dist[n][1] + new1n + d);
            ans = min(ans, new1n + newn1 + d);
        }
    }

    cout << (ans==linf?-1:ans) << endl;
}

signed main () {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t = 1;
    // cin >> t; 
    while (t--) {
        sol();
    }
    return 0;
}

Compilation message

ho_t4.cpp: In function 'void sol()':
ho_t4.cpp:62:13: warning: variable 'temp' set but not used [-Wunused-but-set-variable]
   62 |         pii temp = edge[{par[c], c}];
      |             ^~~~
ho_t4.cpp:70:13: warning: variable 'temp' set but not used [-Wunused-but-set-variable]
   70 |         pii temp = edge[{par[c], c}];
      |             ^~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 860 KB Output is correct
2 Correct 7 ms 604 KB Output is correct
3 Correct 9 ms 952 KB Output is correct
4 Correct 9 ms 860 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 7 ms 600 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 13 ms 344 KB Output is correct
10 Correct 25 ms 860 KB Output is correct
11 Correct 29 ms 1000 KB Output is correct
12 Correct 29 ms 856 KB Output is correct
13 Correct 8 ms 1112 KB Output is correct
14 Correct 9 ms 860 KB Output is correct
15 Correct 8 ms 860 KB Output is correct
16 Correct 11 ms 860 KB Output is correct

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 82 ms 6968 KB Output is correct
2 Correct 61 ms 6936 KB Output is correct
3 Correct 67 ms 6952 KB Output is correct
4 Incorrect 9 ms 860 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 860 KB Output is correct
2 Correct 7 ms 836 KB Output is correct
3 Correct 42 ms 6404 KB Output is correct
4 Correct 9 ms 844 KB Output is correct
5 Correct 50 ms 7672 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 39 ms 7176 KB Output is correct
9 Correct 39 ms 7172 KB Output is correct
10 Correct 46 ms 6796 KB Output is correct
11 Correct 41 ms 6408 KB Output is correct
12 Correct 44 ms 6404 KB Output is correct
13 Incorrect 0 ms 344 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 860 KB Output is correct
2 Correct 7 ms 604 KB Output is correct
3 Correct 9 ms 952 KB Output is correct
4 Correct 9 ms 860 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 7 ms 600 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 13 ms 344 KB Output is correct
10 Correct 25 ms 860 KB Output is correct
11 Correct 29 ms 1000 KB Output is correct
12 Correct 29 ms 856 KB Output is correct
13 Correct 8 ms 1112 KB Output is correct
14 Correct 9 ms 860 KB Output is correct
15 Correct 8 ms 860 KB Output is correct
16 Correct 11 ms 860 KB Output is correct
17 Correct 82 ms 6968 KB Output is correct
18 Correct 61 ms 6936 KB Output is correct
19 Correct 67 ms 6952 KB Output is correct
20 Incorrect 9 ms 860 KB Output isn't correct
21 Halted 0 ms 0 KB -