Submission #1256808

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256808		tradz	Aesthetic (NOI20_aesthetic)	C++20	0 / 100	175 ms	40244 KiB

Aesthetic

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = (1LL<<62);

struct Edge { int u,v; long long w; int idx; };

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, M;
    if(!(cin >> N >> M)) return 0;
    vector<Edge> edges;
    edges.reserve(M);
    vector<vector<pair<int,long long>>> g(N+1);
    for(int i=1;i<=M;i++){
        int a,b; long long w;
        cin >> a >> b >> w;
        edges.push_back({a,b,w,i});
        g[a].push_back({b,w});
        g[b].push_back({a,w});
    }

    auto dijkstra = [&](int src){
        vector<long long> dist(N+1, INF);
        priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<pair<long long,int>>> pq;
        dist[src]=0;
        pq.push({0,src});
        while(!pq.empty()){
            auto [d,u]=pq.top(); pq.pop();
            if(d!=dist[u]) continue;
            for(auto &e: g[u]){
                int v=e.first; long long w=e.second;
                if(dist[v] > dist[u] + w){
                    dist[v] = dist[u] + w;
                    pq.push({dist[v], v});
                }
            }
        }
        return dist;
    };

    auto dist1 = dijkstra(1);
    auto distN = dijkstra(N);
    long long orig = dist1[N];
    // If orig is INF, graph disconnected (but problem guarantees connected)
    // Prepare suffix maximum P_i by original order 1..M
    vector<long long> P(M+2, 0);
    // map index->W
    vector<long long> W(M+1);
    for(auto &e: edges) W[e.idx] = e.w;
    for(int i=M;i>=1;i--){
        P[i] = max(P[i+1], W[i]);
    }

    long long ans = orig;
    for(auto &e: edges){
        int i = e.idx;
        long long add = P[i+1]; // largest W_j with j>i
        if(add==0) continue; // no larger-index edge to replicate
        // two possible orientations
        long long cand1 = INF, cand2 = INF;
        if(dist1[e.u]!=INF && distN[e.v]!=INF){
            cand1 = dist1[e.u] + e.w + add + distN[e.v];
        }
        if(dist1[e.v]!=INF && distN[e.u]!=INF){
            cand2 = dist1[e.v] + e.w + add + distN[e.u];
        }
        long long cand = min(orig, min(cand1, cand2));
        // We want the shortest path length after performing this extension.
        // Using min(orig, ...) is safe because other routes might remain orig.
        if(cand>ans) ans=cand;
    }

    cout << ans << "\n";
    return 0;
}

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