oj.uz

Submission #258081

# Submission time Handle Problem Language Result Execution time Memory
258081 2020-08-05T10:27:00 Z Namnamseo Cities (BOI16_cities) C++17
100 / 100
 2869 ms 97528 KB 
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#define pb push_back
using namespace std;

vector<int> edge[100010];
vector<int> ec[100010];

int root;
int v[5];
int n,k;

void read(int& x){ scanf("%d",&x); }
template<typename T,typename... Args> void read(T& a,Args&... b){ read(a); read(b...); }

void in(){
    int m;
    read(n,k,m,root); --k;
    for(int i=0;i<k;++i) read(v[i]);
    for(;m--;){
        int a,b,c; read(a,b,c);
        edge[a].pb(b); edge[b].pb(a);
        ec[a].pb(c); ec[b].pb(c);
    }
}

typedef long long ll;
typedef pair<ll,int> pli;
typedef pair<int,int> pp;
typedef pair<ll,pp> plp;

ll dijk[100010][16];
ll dtemp[100010];

priority_queue<pli> pq_;
priority_queue<plp> pq;

void dijkstra(int start,bool km1){
    int sv=(km1?v[start]:start);
    for(int i=1;i<=n;++i) dtemp[i]=(1LL<<60);
    dtemp[sv]=0; pq_.push({0ll,sv});
    while(pq_.size()){
        auto tmp=pq_.top(); pq_.pop();
        int me;
        if(tmp.first != -dtemp[me=tmp.second]) continue;
        int sz=edge[me].size();
        for(int i=0;i<sz;++i){
            int nxt=edge[me][i], c=ec[me][i];
            if(dtemp[nxt]>dtemp[me]+c){
                dtemp[nxt]=dtemp[me]+c;
                pq_.push({-dtemp[nxt],nxt});
            }
        }
    }
    if(km1) for(int i=1;i<=n;++i) dijk[i][1<<start]=dtemp[i];
}

void renew(int pos,int mask){
    int om=(((1<<k)-1)^mask);
    int i,m;
    ll base=dijk[pos][mask], tmpdiff;
    for(m=om;m; m=((m-1)&om)){
        tmpdiff = 0;
        for(i=0;i<k;++i){
            if((1&(m>>i))==1){
                tmpdiff += dijk[pos][1<<i];
            }
        }
        if(base+tmpdiff < dijk[pos][mask|m]){
            dijk[pos][mask|m]=base+tmpdiff;
            pq.push({-dijk[pos][mask|m],{pos,mask|m}});
        }
    }
}

int main()
{
    in();
    for(int i=0;i<k;++i) dijkstra(i, true);
    for(int i=1;i<=n;++i){
        int ks1=(1<<k);
        for(int j=1;j<ks1;++j){
            if((j&(j-1)))
                for(int t=0;t<k;++t)
                    if(1&(j>>t)) dijk[i][j] += dijk[i][1<<t];
            pq.push({-dijk[i][j], {i,j}});
        }
    }
    while(pq.size()){
        auto a=pq.top(); pq.pop();
        ll dj=-a.first; int x=a.second.first, y=a.second.second;
        if(dijk[x][y]!=dj) continue;
        int i,sz=edge[x].size(),nxt,cst;
        for(i=0;i<sz;++i){
            nxt=edge[x][i];
            cst=ec  [x][i];
            if(dijk[nxt][y]>dijk[x][y]+cst){
                dijk[nxt][y]=dijk[x][y]+cst;
                pq.push({-dijk[nxt][y], {nxt,y}});
                renew(nxt,y);
            }
        }
    }
    ll ans=(1LL<<62);
    dijkstra(root, false);
    for(int i=1;i<=n;++i){
        ans=min(ans, dijk[i][((1<<k)-1)]+dtemp[i]);
    }
    printf("%lld\n",ans);
    return 0;
}

Compilation message

cities.cpp: In function 'void read(int&)':
cities.cpp:15:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 void read(int& x){ scanf("%d",&x); }
                    ~~~~~^~~~~~~~~

Subtask #1
22.0 / 22.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 596 ms 40040 KB Output is correct
2 Correct 663 ms 40236 KB Output is correct
3 Correct 478 ms 35044 KB Output is correct
4 Correct 110 ms 13176 KB Output is correct
5 Correct 485 ms 33896 KB Output is correct
6 Correct 104 ms 13176 KB Output is correct
7 Correct 6 ms 5376 KB Output is correct
8 Correct 5 ms 5248 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5580 KB Output is correct
2 Correct 7 ms 5504 KB Output is correct
3 Correct 7 ms 5504 KB Output is correct
4 Correct 7 ms 5376 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1331 ms 48348 KB Output is correct
2 Correct 1173 ms 48248 KB Output is correct
3 Correct 858 ms 43352 KB Output is correct
4 Correct 690 ms 31716 KB Output is correct
5 Correct 195 ms 17776 KB Output is correct
6 Correct 109 ms 14968 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2845 ms 64824 KB Output is correct
2 Correct 2869 ms 97528 KB Output is correct
3 Correct 2834 ms 97492 KB Output is correct
4 Correct 1871 ms 59708 KB Output is correct
5 Correct 1667 ms 56388 KB Output is correct
6 Correct 365 ms 24040 KB Output is correct
7 Correct 119 ms 15416 KB Output is correct