Submission #834158

#	Time	Username	Problem	Language	Result	Execution time	Memory
834158		_martynas	Aesthetic (NOI20_aesthetic)	C++11	13 / 100	269 ms	536 KiB

Aesthetic

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

#warning change mxn
const int mxn = 3e3+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 (stderr)

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

• Subtask 1: 5 / 5
• Subtask 2: 8 / 8
• Subtask 3: 0 / 7
• Subtask 4: 0 / 15
• Subtask 5: 0 / 16
• Subtask 6: 0 / 22
• Subtask 7: 0 / 27