oj.uz

Submission #440835

# Submission time Handle Problem Language Result Execution time Memory
440835 2021-07-03T10:39:58 Z nickmet2004 Cities (BOI16_cities) C++11
100 / 100
 1296 ms 39356 KB 
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 5;
int n , k , m , A[6];
int d[6][N] , F[6][6][N] , v[N];
vector<pair<int , int>> adj[N];
void go(int a , int b , int *ans){
    priority_queue<pair<int , int> > pq;
    for(int y = 1; y <= n; ++y) {
        if(b!=0) ans[y] = d[a][y] + d[b][y], pq.push({-ans[y] , y});
        else ans[y] = 1e18;

    }
    if(b==0)pq.push({0 , a}) , ans[a] = 0;
    int u , w;
    while(pq.size()){
        auto T = pq.top(); pq.pop();
        u = T.second , w = -T.first;
        if(v[u])continue;
        v[u]= 1;
        int v , D;
        for(auto V : adj[u]){
            v = V.first , D = V.second;
            if(ans[v] > D + w){ans[v] = D + w; pq.push({-ans[v] , v});}
        }
    }
    memset(v , 0 , sizeof(v));
}
 main (){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> k >> m;
    for(int i = 0; i< k; ++i)cin >> A[i];
    int u , v , w;
    for(int i = 1; i<= m; ++i){
        cin >> u >> v >> w;
        adj[u].emplace_back(v , w);
        adj[v].emplace_back(u , w);
    }
    for(int i = 0; i < k; ++i) go(A[i] , 0 , d[i]);
    for(int i = 0; i< k; ++i){
        for(int j = i + 1; j < k; ++j){
            go(i , j , F[i][j]);
            //for(int x =1; x <= n; ++x)cout << i << " "<< j << " " << x << " " << F[i][j][x] << endl;
        }
    }
    /*
    for(int i = 0; i< k; ++i){
        for(int x= 1; x <= n; ++x)cout << d[i][x] << " ";
        cout << endl;
    }
    */
    if(k == 2)cout << d[0][A[1]]<<endl;
    if(k == 3)cout << F[0][1][A[2]] << endl;
    int ans = 1e18;
    if(k == 4){
        vector<int> P = {0 , 1, 2, 3};
        do{
            if(P[0] > P[1] || P[2] > P[3])continue;
            for(int i = 1; i<= n; ++i)ans = min(ans , F[P[0]][P[1]][i] + F[P[2]][P[3]][i]);
        }while(next_permutation(P.begin(), P.end()));
        cout << ans;
    }
    if(k == 5){
        vector<int> P = {0 ,1 , 2, 3 , 4};
        do{
           if(P[1] > P[2] || P[3] > P[4])continue;
           for(int i = 1; i<= n; ++i)ans = min(ans , F[P[1]][P[2]][i] + F[P[3]][P[4]][i] + d[P[0]][i]);
        }while(next_permutation(P.begin() , P.end()));
        cout << ans;
    }
}

Compilation message

cities.cpp:30:2: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   30 |  main (){
      |  ^~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6588 KB Output is correct
2 Correct 4 ms 6604 KB Output is correct
3 Correct 4 ms 6604 KB Output is correct
4 Correct 4 ms 6604 KB Output is correct
5 Correct 5 ms 6604 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 705 ms 28088 KB Output is correct
2 Correct 647 ms 27548 KB Output is correct
3 Correct 388 ms 20092 KB Output is correct
4 Correct 91 ms 15664 KB Output is correct
5 Correct 410 ms 23540 KB Output is correct
6 Correct 92 ms 15604 KB Output is correct
7 Correct 8 ms 6732 KB Output is correct
8 Correct 6 ms 6792 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 6860 KB Output is correct
2 Correct 8 ms 6860 KB Output is correct
3 Correct 7 ms 6832 KB Output is correct
4 Correct 7 ms 6860 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1057 ms 31112 KB Output is correct
2 Correct 1226 ms 34872 KB Output is correct
3 Correct 668 ms 25364 KB Output is correct
4 Correct 517 ms 28792 KB Output is correct
5 Correct 170 ms 20924 KB Output is correct
6 Correct 88 ms 21308 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1296 ms 35320 KB Output is correct
2 Correct 1288 ms 39356 KB Output is correct
3 Correct 1265 ms 38808 KB Output is correct
4 Correct 796 ms 29320 KB Output is correct
5 Correct 690 ms 30668 KB Output is correct
6 Correct 197 ms 21408 KB Output is correct
7 Correct 93 ms 21540 KB Output is correct