제출 #75171

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
75171		Kamisama	Cities (BOI16_cities)	C++14	74 / 100	6065 ms	175472 KiB

cities

#include <bits/stdc++.h>
#define up(i,a,b) for(int i=a;i<=b;i++)
#define down(i,a,b) for(int i=a;i>=b;i--)
#define rep(i,a,b) for(int i=a;i<b;i++)
#define repd(i,a,b) for(int i=a-1;i>=b;i--)
#define CL(x) (x<<1)
#define CR(x) (x<<1)+1
#define pb push_back
#define bit1(x) __builtin_popcount(x)
#define self (*this)
#define Kamisama

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,int> pli;
typedef pair<ll,pii> plii;
#define x first
#define y second

template<typename T> inline void _read(T &x){
    char ch; x=0; bool neg=false;
    for(ch=getchar();ch<'0'||ch>'9';ch=getchar())
        if(ch=='-') neg=true;
    for(;ch>='0'&&ch<='9';ch=getchar()) x=10*x+ch-'0';
    if(neg) x=-x;
}
#define read(a) _read(a)
#define Read(a,b) _read(a),_read(b)
#define READ(a,b,c) _read(a),_read(b),_read(c)

const int maxn=1e5+7;
const int Nblocks=400;
const int maxS=(1<<5)+7;
const ll mod=9901;
const int inf=1e9+7;
const ll linf=1e16+9;
const double pi=4*atan(1);
const ll Radix=1e9;
const int Length=9;
const int MaxDigit=2e4+1;
const int nDigits=MaxDigit/Length+1;

/// Bit Manipulation
inline int SetBit(int x,int k){return x|(1<<k);}
inline bool IsSubSet(int x,int y){return (x&y)==0;}
/// End of Bit Manipulation

int n,m,k,city[maxn];
ll f[maxn][maxS];
vector<int> SubS[maxS];
vector<pli> a[maxn];
priority_queue< plii,vector<plii>,greater<plii> > q;

inline void Enter(){
    READ(n,k,m);
    up(i,1,k){
        int p;
        read(p);
        city[p]=i;
    }
    up(i,1,m){
        int u,v,w;
        READ(u,v,w);
        a[u].pb(pli(w,v));
        a[v].pb(pli(w,u));
    }
    //up(i,1,n) sort(a[i].begin(),a[i].end());
}

inline void Prepare(){
    int MaxState=(1<<k);
    rep(i,0,MaxState) rep(j,0,MaxState) if(IsSubSet(i,j)) SubS[i].pb(j);
    fill_n(&f[0][0],maxn*maxS,linf);
    up(i,1,n) if(city[i]) f[i][1<<(city[i]-1)]=0,q.push(plii(0,pii(i,1<<(city[i]-1))));

}

inline ll Dijkstra(){
    while(q.size()){
        ll w=q.top().x;
        auto u=q.top().y;
        q.pop();
        //cerr<<u<<' '<<State<<' '<<w<<'\n';
        if(w>f[u.x][u.y]) continue;
        if(u.y==(1<<k)-1) return w;
        for(auto v: a[u.x]){
            ll Cost=f[u.x][u.y]+v.x;
            int State=u.y;
            if(city[v.y]) State=SetBit(State,city[v.y]-1);
            if(f[v.y][State]>Cost){
                f[v.y][State]=Cost;
                q.push(plii(Cost,pii(v.y,State)));
            }
            for(int SubSet: SubS[u.y]){
                ll NewCost=Cost+f[v.y][SubSet];
                int NewState=State|SubSet;
                if(f[v.y][NewState]>NewCost){
                    f[v.y][NewState]=NewCost;
                    q.push(plii(NewCost,pii(v.y,NewState)));
                }
            }
        }
    }
    ll Res=linf;
    up(i,1,n) Res=min(Res,f[i][(1<<k)-1]);
    return Res;
}

inline void Solve(){
    cout<<Dijkstra();
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL),cout.tie(NULL);
    #ifndef Kamisama
    freopen("TEST.INP","r",stdin);
    freopen("TEST.OUT","w",stdout);
    #endif // Kamisama

    Enter();
    Prepare();
    Solve();

    return 0;
}

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