제출 #259750

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
259750		Autoratch	Cities (BOI16_cities)	C++14	0 / 100	192 ms	17400 KiB

cities

#include <bits/stdc++.h>
using namespace std;
#define pii pair<long long,int>

const int N = 1e5 + 1;
const int K = 6;

int n,k,m;
long long ans = LLONG_MAX;
int s[K],idx[N];
vector<pair<int,int> > adj[N];
long long dist[K][N];
bool visited[N];
priority_queue<pii,vector<pii>,greater<pii> > q;
vector<int> perm;

void dijk(int k,long long (&dist)[N])
{
    for(int i = 1;i <= n;i++) visited[i] = false;
    for(int i = 1;i <= n;i++) dist[i] = INT_MAX;
    dist[s[k]] = 0;
    q.push({0,s[k]});
    while(!q.empty())
    {
        int u = q.top().second;
        q.pop();
        if(visited[u]) continue;
        visited[u] = true;
        for(auto [d,v] : adj[u]) if(dist[u]+d<dist[v]) dist[v] = dist[u]+d,q.push({dist[v],v});
    }
}

long long dis(int a,int b){ return dist[idx[a]][b]; }

void solve2(){ ans = min(ans,dis(perm[0],perm[1])); }

void solve3(){ for(int i = 1;i <= n;i++) ans = min(ans,dis(perm[0],i)+dis(perm[1],i)+dis(perm[2],i)); }

void solve4()
{ 
    ans = min(ans,dis(perm[0],perm[1])+dis(perm[0],perm[2])+dis(perm[0],perm[3])); 
    ans = min(ans,dis(perm[0],perm[1])+dis(perm[1],perm[2])+dis(perm[2],perm[3]));
}

void solve5()
{
    ans = min(ans,dis(perm[0],perm[1])+dis(perm[1],perm[2])+dis(perm[2],perm[3])+dis(perm[3],perm[4]));
    ans = min(ans,dis(perm[0],perm[1])+dis(perm[0],perm[2])+dis(perm[0],perm[3])+dis(perm[0],perm[4]));
    ans = min(ans,dis(perm[0],perm[1])+dis(perm[1],perm[2])+dis(perm[1],perm[3])+dis(perm[3],perm[4]));
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    
    cin >> n >> k >> m;
    for(int i = 1;i <= k;i++) cin >> s[i],idx[s[i]] = i;
    for(int i = 1;i <= m;i++) 
    {
        int a,b,d;
        cin >> a >> b >> d;
        adj[a].push_back({d,b});
        adj[b].push_back({d,a});
    }
    for(int i = 1;i <= k;i++) dijk(i,dist[i]),perm.push_back(s[i]);
    sort(perm.begin(),perm.end());
    do{
        if(k==2) solve2();
        else if(k==3) solve3();
        else if(k==4) solve4();
        else solve5();
    }while(next_permutation(perm.begin(),perm.end()));
    cout << ans;
}

컴파일 시 표준 에러 (stderr) 메시지

cities.cpp: In function 'void dijk(int, long long int (&)[100001])':
cities.cpp:29:18: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
         for(auto [d,v] : adj[u]) if(dist[u]+d<dist[v]) dist[v] = dist[u]+d,q.push({dist[v],v});
                  ^

• Subtask 1: 0 / 22
• Subtask 2: 0 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 23
• Subtask 5: 0 / 26