oj.uz

Submission #91816

# Submission time Handle Problem Language Result Execution time Memory
91816 2018-12-30T07:56:04 Z Mercenary Cities (BOI16_cities) C++11
100 / 100
 2578 ms 44972 KB 
#include<bits/stdc++.h>

using namespace std;
#define taskname "BOI16CITIES"
#define pb	push_back
typedef long double ld;
typedef long long ll;
const int maxn = 1e5 + 5;
const int maxs = 1 << 5;
typedef pair<int,int> ii;
typedef pair<ll,int> lli;
const ll inf = 1e18;

#define mp make_pair
ll d[maxs][maxn];
int n , m , k;
vector<ii> adj[maxn];

void dij(ll d[maxn])
{
    priority_queue<lli,vector<lli>,greater<lli>> pq;
    for(int i = 1 ; i <= n ; ++i)pq.push(mp(d[i] , i));
    while(!pq.empty())
    {
        auto u = pq.top();pq.pop();
        if(d[u.second] != u.first)continue;
        for(auto c : adj[u.second])
        {
            if(d[c.first] > u.first + c.second)
            {
                d[c.first] = u.first + c.second;
                pq.push(mp(d[c.first],c.first));
            }
        }
    }
}

void enter()
{
    cin >> n >> k >> m;
    for(int i = 0 ; i < (1 << k) ; ++i)
        for(int j = 1 ; j <= n ; ++j)
            d[i][j] = inf;
    for(int i = 0 ; i < k ; ++i)
    {
        int u;cin >> u;
        d[1 << i][u] = 0;
    }
    for(int i = 1 ; i <= m ; ++i)
    {
        int u , v , c;cin >> u >> v >> c;
        adj[u].pb(mp(v,c));
        adj[v].pb(mp(u,c));
    }
}

void solve()
{
    for(int i = 0 ; i < (1 << k) ; ++i)
    {
        for(int j = i ; j > 0 ; j = (j - 1) & i)
            for(int t = 1 ; t <= n ; ++t)
                d[i][t] = min(d[i][t] , d[j][t] + d[i ^ j][t]);
        dij(d[i]);
    }
    ll res = inf;
    for(int i = 1 ; i <= n ; ++i)res = min(res , d[(1 << k) - 1][i]);
    cout << res;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	if(fopen(taskname".INP","r"))
        freopen(taskname".INP", "r",stdin) ,
        freopen(taskname".OUT", "w",stdout);
    enter();
    solve();
}

Compilation message

cities.cpp: In function 'int main()':
cities.cpp:76:44: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(taskname".INP", "r",stdin) ,
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~
         freopen(taskname".OUT", "w",stdout);
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 
cities.cpp:76:44: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]

Subtask #1
22.0 / 22.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 736 ms 26116 KB Output is correct
2 Correct 674 ms 26008 KB Output is correct
3 Correct 386 ms 18008 KB Output is correct
4 Correct 71 ms 10936 KB Output is correct
5 Correct 431 ms 22828 KB Output is correct
6 Correct 73 ms 10872 KB Output is correct
7 Correct 7 ms 2936 KB Output is correct
8 Correct 6 ms 2936 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 3064 KB Output is correct
2 Correct 9 ms 3064 KB Output is correct
3 Correct 7 ms 2936 KB Output is correct
4 Correct 6 ms 2936 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1276 ms 32568 KB Output is correct
2 Correct 1222 ms 32416 KB Output is correct
3 Correct 940 ms 24304 KB Output is correct
4 Correct 663 ms 22688 KB Output is correct
5 Correct 178 ms 14428 KB Output is correct
6 Correct 81 ms 12768 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2578 ms 44972 KB Output is correct
2 Correct 2494 ms 44900 KB Output is correct
3 Correct 2307 ms 44956 KB Output is correct
4 Correct 1781 ms 36852 KB Output is correct
5 Correct 1474 ms 29008 KB Output is correct
6 Correct 295 ms 15624 KB Output is correct
7 Correct 90 ms 12796 KB Output is correct