oj.uz

Submission #34612

# Submission time Handle Problem Language Result Execution time Memory
34612 2017-11-14T12:34:23 Z Extazy Cities (BOI16_cities) C++11
100 / 100
 3509 ms 104940 KB 
#include <bits/stdc++.h>
#define endl '\n'

using namespace std;

const int N = 1<<18;
const long long INF = 1000000000000000007;

struct edge {
    int to,w;
    edge(){}
    edge(int a, int b) {
        to=a;
        w=b;
    }
};

struct el {
    int vertex;
    long long cost;
    el(){}
    el(int a, long long b) {
        vertex=a;
        cost=b;
    }
    bool operator <(const el &a) const {
        return cost>a.cost;
    }
};

int n,k,m,important[8];
vector < edge > v[N];
long long int dist[1<<5][N];
char buff[(1<<24) + 7],*buffp=buff;
bool used[N];

void read(int &res) {
    res=0;
    while(*buffp<48) ++buffp;
    while(*buffp>47) res=(res<<3)+(res<<1)+*buffp++-48;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    fread(buff,1,sizeof(buff),stdin);
    int x,y,z;
    int j; int i;

    read(n);
    read(k);
    read(m);
    for(i=1;i<=k;i++) {
        read(important[i]);
    }

    for(i=1;i<=m;i++) {
        read(x);
        read(y);
        read(z);
        v[x].push_back(edge(y,z));
        v[y].push_back(edge(x,z));
    }

    for(i=0;i<(1<<k);i++) for(j=1;j<=n;j++) dist[i][j]=INF;

    for(i=0;i<k;i++) {
        dist[1<<i][important[i+1]]=0;
    }

    for(i=1;i<=n;i++) {
        dist[0][i]=0;
    }

    for(int mask=1;mask<(1<<k);mask++) {
        priority_queue < el > q;

        for(int submask1=0;submask1<mask;submask1++) if((mask|submask1)==mask) {
            int submask2=(mask^submask1);
            if(submask2>submask1) continue;
            for(i=1;i<=n;i++) {
                long long current_distance=dist[submask1][i]+dist[submask2][i];
                if(current_distance<dist[mask][i]) {
                    dist[mask][i]=current_distance;
                }
            }
        }

        for(i=1;i<=n;i++) if(dist[mask][i]!=INF) q.push(el(i,dist[mask][i]));

        fill(used+1,used+1+n,false);

        while(!q.empty()) {
            el curr=q.top();
            q.pop();

            if(used[curr.vertex]) continue;
            used[curr.vertex]=true;
            
            for(i=0;i<(int)(v[curr.vertex].size());i++) {
                long long current_distance=v[curr.vertex][i].w+curr.cost;
                if(current_distance<dist[mask][v[curr.vertex][i].to]) {
                    dist[mask][v[curr.vertex][i].to]=current_distance;
                    q.push(el(v[curr.vertex][i].to,current_distance));
                }
            }
        }
    }

    long long ans=INF;
    for(i=1;i<=n;i++) {
        ans=min(ans,dist[(1<<k)-1][i]);
    }

    printf("%lld\n", ans);

    return 0;
}

Compilation message

cities.cpp: In function 'int main()':
cities.cpp:46:37: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     fread(buff,1,sizeof(buff),stdin);
                                     ^

Subtask #1
22.0 / 22.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 813 ms 104936 KB Output is correct
2 Correct 679 ms 104888 KB Output is correct
3 Correct 373 ms 97756 KB Output is correct
4 Correct 26 ms 95148 KB Output is correct
5 Correct 306 ms 102896 KB Output is correct
6 Correct 23 ms 95020 KB Output is correct
7 Correct 3 ms 90636 KB Output is correct
8 Correct 0 ms 90636 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 90636 KB Output is correct
2 Correct 6 ms 90660 KB Output is correct
3 Correct 0 ms 90500 KB Output is correct
4 Correct 3 ms 90636 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1483 ms 104940 KB Output is correct
2 Correct 1519 ms 104744 KB Output is correct
3 Correct 826 ms 97760 KB Output is correct
4 Correct 759 ms 100372 KB Output is correct
5 Correct 133 ms 96728 KB Output is correct
6 Correct 29 ms 96668 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3446 ms 104936 KB Output is correct
2 Correct 3239 ms 104932 KB Output is correct
3 Correct 3509 ms 104792 KB Output is correct
4 Correct 2036 ms 97760 KB Output is correct
5 Correct 1369 ms 100356 KB Output is correct
6 Correct 249 ms 96728 KB Output is correct
7 Correct 43 ms 96664 KB Output is correct