Submission #1134121

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134121		Aviansh	Aesthetic (NOI20_aesthetic)	C++20	13 / 100	2095 ms	28240 KiB

Aesthetic

#include <bits/stdc++.h>

using namespace std;

int n,m;

long long shortest(vector<array<int,2>>(&g)[]){
    priority_queue<array<long long,2>,vector<array<long long,2>>,greater<array<long long,2>>>pq;
    pq.push({0,0});
    long long dist[n];
    fill(dist,dist+n,-1);
    while(!pq.empty()){
        array<long long,2> a = pq.top();
        pq.pop();
        if(dist[a[1]]==-1){
            dist[a[1]]=a[0];
        }
        else{
            continue;
        }
        for(array<int,2>e:g[a[1]]){
            pq.push({a[0]+e[1],e[0]});
        }
    }
    return dist[n-1];
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    vector<array<int,2>>g[n];
    array<int,3>edges[m];
    for(int i = 0;i<m;i++){
        cin >> edges[i][0];
        cin >> edges[i][1];
        cin >> edges[i][2];
        edges[i][0]--;
        edges[i][1]--;
        g[edges[i][0]].push_back({edges[i][1],edges[i][2]});
        g[edges[i][1]].push_back({edges[i][0],edges[i][2]});
    }
    int pref[m];
    pref[m-1]=edges[m-1][2];
    for(int i = m-2;i>=0;i--){
        pref[i]=max(edges[i][2],pref[i+1]);
    }
    long long ans = shortest(g);
    for(int i = 0;i<m-1;i++){
        int j = -1;
        for(array<int,2>e1:g[edges[i][0]]){
            j++;
            if(e1[0]!=edges[i][1])
                continue;
            int temp = edges[i][2];
            g[edges[i][0]][j][1]+=pref[i+1];
            for(int k = 0;k<g[edges[i][1]].size();k++){
                if(g[edges[i][1]][k][0]!=edges[i][0])
                    continue;
                g[edges[i][1]][k][1]+=pref[i+1];
                ans=max(ans,shortest(g));
                g[edges[i][1]][k][1]=temp;
            }
            g[edges[i][0]][j][1]=temp;
        }
    }
    cout << ans;
    return 0;
}

• 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