oj.uz

Submission #56109

# Submission time Handle Problem Language Result Execution time Memory
56109 2018-07-10T04:16:56 Z 김현수(#2106) Cities (BOI16_cities) C++11
100 / 100
 3281 ms 101240 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 1e18;

ll n, g, m, imp[5], dist[32][100005], ans = inf;
vector<ll> cg[100005], cv[100005];
priority_queue<pair<ll,ll> >pq;

int main()
{
    scanf("%lld%lld%lld",&n,&g,&m);
    for(int i=0;i<g;i++) scanf("%lld",&imp[i]);
    for(int i=1;i<=m;i++) {
        ll A, B, C;
        scanf("%lld%lld%lld",&A,&B,&C);
        cg[A].push_back(B); cv[A].push_back(C);
        cg[B].push_back(A); cv[B].push_back(C);
    }
    for(int i=1;i<(1<<g);i++) {
        for(int j=1;j<=n;j++) dist[i][j] = inf;
        if(i&(i-1)) {
            for(int j=1;j<i;j++) {
                if((i&j) != j) continue;
                for(int k=1;k<=n;k++) {
                    dist[i][k] = min(dist[j][k] + dist[i-j][k], dist[i][k]);
                }
            }
            for(int j=1;j<=n;j++) pq.push({-dist[i][j], j});
        }
        else {
            for(int j=0;j<g;j++) {
                if((1<<j) == i) {
                    dist[i][imp[j]] = 0;
                    pq.push({0, imp[j]});
                }
            }
        }
        while(!pq.empty()) {
            ll cur = pq.top().second, val = -pq.top().first;
            pq.pop();
            if(dist[i][cur] != val) continue;
            for(int j=0;j<cg[cur].size();j++) {
                if(dist[i][cg[cur][j]] > val + cv[cur][j]) {
                    dist[i][cg[cur][j]] = val + cv[cur][j];
                    pq.push({-dist[i][cg[cur][j]], cg[cur][j]});
                }
            }
        }
    }
    for(int i=1;i<=n;i++) {
        ans = min(ans, dist[(1<<g)-1][i]);
    }
    printf("%lld",ans);
}

Compilation message

cities.cpp: In function 'int main()':
cities.cpp:43:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j=0;j<cg[cur].size();j++) {
                         ~^~~~~~~~~~~~~~~
cities.cpp:12:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld%lld%lld",&n,&g,&m);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
cities.cpp:13:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=0;i<g;i++) scanf("%lld",&imp[i]);
                          ~~~~~^~~~~~~~~~~~~~~~
cities.cpp:16:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld%lld%lld",&A,&B,&C);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 7 ms 5228 KB Output is correct
3 Correct 6 ms 5340 KB Output is correct
4 Correct 6 ms 5452 KB Output is correct
5 Correct 6 ms 5584 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 977 ms 30008 KB Output is correct
2 Correct 809 ms 33660 KB Output is correct
3 Correct 527 ms 33660 KB Output is correct
4 Correct 138 ms 33660 KB Output is correct
5 Correct 562 ms 42688 KB Output is correct
6 Correct 130 ms 42688 KB Output is correct
7 Correct 10 ms 42688 KB Output is correct
8 Correct 10 ms 42688 KB Output is correct

Subtask #3
15.0 / 15.0

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

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1769 ms 58460 KB Output is correct
2 Correct 1748 ms 62212 KB Output is correct
3 Correct 1165 ms 62212 KB Output is correct
4 Correct 999 ms 62212 KB Output is correct
5 Correct 335 ms 62212 KB Output is correct
6 Correct 150 ms 62212 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3168 ms 93180 KB Output is correct
2 Correct 3281 ms 97188 KB Output is correct
3 Correct 2993 ms 101240 KB Output is correct
4 Correct 2464 ms 101240 KB Output is correct
5 Correct 1807 ms 101240 KB Output is correct
6 Correct 486 ms 101240 KB Output is correct
7 Correct 196 ms 101240 KB Output is correct