Submission #976510

#	Time	Username	Problem	Language	Result	Execution time	Memory
976510		Haanhtien	Relay Marathon (NOI20_relaymarathon)	C++14	5 / 100	164 ms	79108 KiB

RelayMarathon

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define ii pair<ll, ll>
#define fi first
#define se second

struct datax{
    ll u, v, w;
};

ll n, m, k, cities[100005], ans, t, u, v, w, dist[100005], h[100005];
ll flat[100005], d[505][505], f[505], g[505];

vector<ii> adj[100005];
datax queries[400005];

bool check(ll x, ll y, ll z, ll t){
    return (x!=y&&x!=z&&x!=t&&y!=z&&y!=t&&z!=t);
}

void dijkstra(ll s){
    priority_queue<ii, vector<ii>, greater<ii>> pq;
    for(int i=1; i<=n; i++) dist[i] = 1e9;
    dist[s] = 0;
    pq.push({0, s});
    while(!pq.empty()){
        ll val = pq.top().fi;
        ll u = pq.top().se;
        pq.pop();
        if(dist[u]!=val) continue;
        for(auto edge:adj[u]){
            ll v = edge.fi;
            ll w = edge.se;
            if(dist[v]>dist[u]+w){
                dist[v] = dist[u]+w;
                pq.push({dist[v], v});
            }
        }
    }
}

void dijkstra2(){
    priority_queue<ii, vector<ii>, greater<ii>> pq;
    for(int i=1; i<=n; i++) dist[i] = 1e9;
    for(int i=1; i<=k; i++){
        dist[cities[i]]=0;
        pq.push({0, cities[i]});
        h[cities[i]] = cities[i];
    }
    while(!pq.empty()){
        ll val = pq.top().fi;
        ll u = pq.top().se;
        pq.pop();
        if(dist[u]!=val) continue;
        for(auto edge:adj[u]){
            ll v = edge.fi;
            ll w = edge.se;
            if(dist[v]==dist[u]+w) flat[v] = 1;
            if(dist[v]>dist[u]+w){
                dist[v] = dist[u]+w;
                h[v] = h[u];
                flat[v]=0;
                pq.push({dist[v], v});
            }

        }
    }
}
void inp(){
    cin >> n >> m >> k;
    for(int i=1; i<=m; i++){
        cin >> u >> v >> w;
        queries[i] = {u, v, w};
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    for(int i=1; i<=k; i++) cin >> cities[i];
}

void sub1(){
    ll ans=LLONG_MAX;
    for(int i=1; i<=n; i++){
        dijkstra(i);
        for(int j=1; j<=n; j++)
            d[i][j] = dist[j];
    }

    for(int x=1; x<=k; x++){
        for(int y=1; y<=k; y++){
            for(int z=1; z<=k; z++){
                for(t=1; t<=k; t++){
                    if(check(x, y, z, t)){
                        ans = min(ans, d[cities[x]][cities[y]]+d[cities[z]][cities[t]]);
                    }
                }
            }
        }
    }
    cout << ans;
}

void sub2(){
    for(int i=1; i<=n; i++){
        dijkstra(i);
        for(int j=1; j<=n; j++)
            d[i][j] = dist[j];
        f[i] = cities[1];
        g[i] = cities[1];
        if(i==cities[1]){
            f[i] = cities[2];
            g[i] = cities[2];
        }
    }
    //cout << d[3][1] << '\n';
    for(int i=1; i<=k; i++){
        for(int j=1; j<=k; j++){
            if(i==j) continue;
            ll x = cities[i];
            ll y = cities[j];
            if(d[x][y]<d[x][f[x]]){
                f[x]=y;
            }
            else{
                if(d[x][y]<d[x][g[x]]){
                    g[x]=y;
                }
            }
        }
        //cout << f[cities[i]] << '\n';
    }
    ll ans=LLONG_MAX;
    for(int i=1; i<=k; i++){
        for(int j=i+1; j<=k; j++){
            ll x = cities[i];
            ll y = cities[j];
            if(f[x]!=f[y]&&f[x]!=y&&f[y]!=x) ans = min(ans, d[x][f[x]]+d[y][f[y]]);
            else
                if(g[x]!=y&&f[y]!=x) ans = min(ans, d[x][g[x]]+d[y][f[y]]);
                if(f[x]!=y&&g[y]!=x) ans = min(ans, d[x][f[x]]+d[y][g[y]]);
        }
    }
    cout << ans;

}

void sub3(){
    dijkstra2();
    ll ans=LLONG_MAX;
    for(int i=1; i<=m; i++){
        ll u = queries[i].u, v = queries[i].v, w = queries[i].w;
        if(u==1||u==2) continue;
        if(flat[u]||flat[v]||h[u]!=h[v]){
            ans = min(ans, dist[u]+dist[v]+w);
            //cout << dist[u] << ' '  << dist[v] << '\n';
            //cout << flat[u] << ' ' <<flat[v] << '\n';
        }
    }
    cout << ans+1;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    //freopen("cities.inp", "r", stdin);
    //freopen("cities.out", "w", stdout);
    inp();
    if(n<=50) sub1();
    else if(n<=500&&m<=4000) sub2();
    else sub3();
    return 0;
}

Compilation message (stderr)

RelayMarathon.cpp: In function 'void sub2()':
RelayMarathon.cpp:139:13: warning: this 'else' clause does not guard... [-Wmisleading-indentation]
  139 |             else
      |             ^~~~
RelayMarathon.cpp:141:17: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'else'
  141 |                 if(f[x]!=y&&g[y]!=x) ans = min(ans, d[x][f[x]]+d[y][g[y]]);
      |                 ^~

• Subtask 1: 5 / 5
• Subtask 2: 0 / 12
• Subtask 3: 0 / 25
• Subtask 4: 0 / 58