oj.uz

Submission #834157

# Submission time Handle Problem Language Result Execution time Memory
834157 2023-08-22T11:21:08 Z _martynas Aesthetic (NOI20_aesthetic) C++11
0 / 100
 1 ms 360 KB 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

#warning change mxn
const int mxn = 3e1+5;
const ll inf = 1e16;

struct Edge {
    int to, id;
};

int n, m;
int A[mxn], B[mxn];
vector<Edge> adj[mxn];
ll W[mxn];

vector<ll> get_min_dist(int start, int forb) {
    vector<long long> dist(n+1, inf);
    priority_queue<pair<ll, int>> pq;
    dist[start] = 0;
    pq.push({-dist[start], start});;
    while(!pq.empty()) {
        ll d = -pq.top().first;
        int a = pq.top().second;
        pq.pop();
        if(dist[a] != d) continue;
        for(auto e : adj[a]) if(dist[e.to] > d+W[e.id] && e.id != forb) {
            dist[e.to] = d+W[e.id];
            pq.push({-dist[e.to], e.to});
        }
    }
    return dist;
}

int main(int argc, char const *argv[]) {
    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        cin >> A[i] >> B[i] >> W[i];
        adj[A[i]].push_back({B[i], i});
        adj[B[i]].push_back({A[i], i});
    }
    vector<ll> from1, fromn;
    from1 = get_min_dist(1, -1);
    fromn = get_min_dist(n, -1);
    ll mxw = W[m];
    vector<ll> ans(m);
    for(int i = m-1; i >= 1; i--) {
        ll nw = W[i]+mxw;
        ll mndist = inf;
        mndist = min(mndist, from1[A[i]]+fromn[B[i]]+nw);
        mndist = min(mndist, from1[B[i]]+fromn[A[i]]+nw);
        ans[i] = mndist;
        mxw = max(mxw, W[i]);
    }
    for(int i = m-1; i >= 1; i--) {
        ans[i] = min(ans[i], get_min_dist(1, i)[n]);
    }
    ll answer = 0;
    for(int i = 1; i < m; i++) {
        answer = max(answer, ans[i]);
    }
    cout << answer << "\n";
    return 0;
}

Compilation message

Aesthetic.cpp:7:2: warning: #warning change mxn [-Wcpp]
    7 | #warning change mxn
      |  ^~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 360 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -