제출 #1281972

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1281972		vuquangsang	Cities (BOI16_cities)	C++20	100 / 100	1037 ms	38308 KiB

cities

#include <bits/stdc++.h>
using namespace std;

#define     el "\n"
#define     FOR(i,a,b) for(int i = (a), _b = (b); i <= _b; i++)
#define     FORD(i,a,b) for(int i = (a), _b = (b); i >= _b; i--)
#define     pb push_back
#define     fi first
#define     se second
#define     all(x) x.begin(),x.end()
#define     lg(x) __lg(x)
#define     alla(a,n) a+1,a+n+1


template <class T> bool maxi(T &x, T y) { if(x < y) { x = y ; return true ;} return false;}
template <class T> bool mini(T &x, T y) { if(x > y) { x = y ; return true ;} return false;}

const int N = 2e5 + 2;


int n, k, m, a[N];
vector<pair<int, int>> adj[N];
void inp()
{
    cin >> n >> k >> m;
    FOR(i, 1, k) cin >> a[i];
    int x, y, w;
    FOR(i, 1, m) {
        cin >> x >> y >> w;
        adj[x].pb({y, w});
        adj[y].pb({x, w});
    }
}

/*  4 months to VOI
    Try your best
    No regrets */

namespace sub1
{
    const long long INF = 1e16 + 2;
    struct eg
    {
        int u;
        long long val;
        bool operator<(const eg&other) const
        {
            return val > other.val;
        }
    };
    long long dist[35][N];
    void slv()
    {
        FOR(msk, 0, (1 << k) - 1) FOR(i, 1, n) dist[msk][i] = INF;

        priority_queue<eg> pq;
        FOR(i, 0, k - 1) {
            dist[(1 << i)][a[i + 1]] = 0;
        }
        FOR(msk, 0, (1 << k) - 1) {
            FOR(preMsk, 0, msk / 2) if((msk & preMsk) == preMsk) {
                int sufMsk = msk ^ preMsk;
                FOR(i, 1, n) mini(dist[msk][i], dist[preMsk][i] + dist[sufMsk][i]);
            }
            FOR(i, 1, n) if(dist[msk][i] != INF) pq.push({i, dist[msk][i]});
            while(!pq.empty()) {
                int u = pq.top().u;
                long long val = pq.top().val;
                pq.pop();

                if(val > dist[msk][u]) continue;

                for(pair<int, int> x : adj[u]) {
                    int v = x.fi, w = x.se;
                    if(mini(dist[msk][v], dist[msk][u] + w)) {
                        pq.push({v, dist[msk][v]});
                    }
                }
            }
        }
        long long ans = INF;
        FOR(i, 1, n) mini(ans, dist[(1 << k) - 1][i]);
        cout << ans;
    }
}

/* Code slowly, think carefully */

main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    #define __Azul__ "fc111_city"
    if(fopen(__Azul__".inp", "r")) {
        freopen(__Azul__".inp", "r", stdin);
        freopen(__Azul__".out", "w", stdout);
    }

    bool qs = 0;

    int T = 1;
    if(qs) cin >> T;
    while(T--) {
        inp();
        sub1::slv();
    }

    cerr << "\nTime" << 0.001 * clock() << "s "; return 0;


}

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

cities.cpp:89:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   89 | main()
      | ^~~~
cities.cpp: In function 'int main()':
cities.cpp:95:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |         freopen(__Azul__".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
cities.cpp:96:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |         freopen(__Azul__".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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