oj.uz

Submission #81467

# Submission time Handle Problem Language Result Execution time Memory
81467 2018-10-24T18:46:58 Z igzi Cities (BOI16_cities) C++17
100 / 100
 4148 ms 45244 KB 
#include <bits/stdc++.h>
#define INF 100000000000000000
#define maxN 100002

using namespace std;

long long n,m,k,t,i,j,x,y,z,dp[35][maxN];
vector < pair<long long,long long> > adj[maxN];
vector <long long> v;
bool mar[maxN];


int main()
{
    cin>>n>>k>>m;
    for(i=0;i<k;i++){
        cin>>x;
        x--;
        v.push_back(x);
    }
    for(i=0;i<m;i++){
        cin>>x>>y>>z;
        x--;
        y--;
        adj[x].push_back(make_pair(y,z));
        adj[y].push_back(make_pair(x,z));
    }
    for(i=0;i<32;i++){
        for(j=0;j<n;j++) dp[i][j]=INF;
    }
    for(i=0;i<v.size();i++){
        dp[1<<i][v[i]]=0;
    }
    for(i=0;i<pow(2,k);i++){
        for(j=0;j<n;j++){
            for(t=0;t<min(i,i/2+2);t++){
                dp[i][j]=min(dp[i][j],dp[t][j]+dp[i^t][j]);
            }
        }
        priority_queue <pair<long long,long long>, vector<pair<long long,long long>> , greater<pair<long long,long long>>> pq;
        for(j=0;j<n;j++){
            pq.push({dp[i][j],j});
        }
        memset(mar,false,n+2);
        while(!pq.empty()){
            x=pq.top().second;
            pq.pop();
            if(mar[x]) continue;
            for(j=0;j<adj[x].size();j++){
                if(dp[i][x]+adj[x][j].second<dp[i][adj[x][j].first]){
                    dp[i][adj[x][j].first]=dp[i][x]+adj[x][j].second;
                    pq.push({dp[i][adj[x][j].first],adj[x][j].first});
                }
            }
        }
    }
    long long ans=INF;
    for(i=0;i<n;i++){
        ans=min(ans,dp[(1<<k)-1][i]);
    }
    cout<<ans<<endl;
    return 0;
}

Compilation message

cities.cpp: In function 'int main()':
cities.cpp:31:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<v.size();i++){
             ~^~~~~~~~~
cities.cpp:49:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(j=0;j<adj[x].size();j++){
                     ~^~~~~~~~~~~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2808 KB Output is correct
2 Correct 5 ms 3068 KB Output is correct
3 Correct 5 ms 3120 KB Output is correct
4 Correct 4 ms 3120 KB Output is correct
5 Correct 5 ms 3120 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1250 ms 45244 KB Output is correct
2 Correct 1090 ms 45244 KB Output is correct
3 Correct 713 ms 45244 KB Output is correct
4 Correct 289 ms 45244 KB Output is correct
5 Correct 721 ms 45244 KB Output is correct
6 Correct 273 ms 45244 KB Output is correct
7 Correct 10 ms 45244 KB Output is correct
8 Correct 8 ms 45244 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 45244 KB Output is correct
2 Correct 13 ms 45244 KB Output is correct
3 Correct 10 ms 45244 KB Output is correct
4 Correct 11 ms 45244 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2090 ms 45244 KB Output is correct
2 Correct 1888 ms 45244 KB Output is correct
3 Correct 1335 ms 45244 KB Output is correct
4 Correct 1223 ms 45244 KB Output is correct
5 Correct 490 ms 45244 KB Output is correct
6 Correct 350 ms 45244 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4098 ms 45244 KB Output is correct
2 Correct 4148 ms 45244 KB Output is correct
3 Correct 3922 ms 45244 KB Output is correct
4 Correct 2654 ms 45244 KB Output is correct
5 Correct 2277 ms 45244 KB Output is correct
6 Correct 674 ms 45244 KB Output is correct
7 Correct 361 ms 45244 KB Output is correct