Submission #91816

#	Time	Username	Problem	Language	Result	Execution time	Memory
91816		Mercenary	Cities (BOI16_cities)	C++11	100 / 100	2578 ms	44972 KiB

cities

#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 (stderr)

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 / 22
• Subtask 2: 14 / 14
• Subtask 3: 15 / 15
• Subtask 4: 23 / 23
• Subtask 5: 26 / 26