Submission #26067

#TimeUsernameProblemLanguageResultExecution timeMemory
26067oneshadabCities (BOI16_cities)C++14
100 / 100
3216 ms122904 KiB
#include <bits/stdc++.h> using namespace std; /* Template Begins */ #define FOR(i,N) FORR(i, 0, N) #define FORR(i,a,b) FOTR(i, a, b, 1) #define FOTR(i,a,b,c) for(int i=(a);i<(b);i+=(c)) #define FOREACH(it, x) for(__typeof__((x).begin()) it=(x).begin();it!=(x).end();it++) #define MEM(a,x) memset(a,x,sizeof(a)) #define BCHK(a,x) (((a)>>(x))&1) #define BSET(a,x) ((a)|(1<<(x))) #define BCLR(a,x) ((a)&(~(1<<(x)))) #define BTGL(a,x) ((a)^(1<<(x))) #define FMT(...) (sprintf(CRTBUFF, __VA_ARGS__)?CRTBUFF:0) #define read() freopen("input.txt","r",stdin) #define write() freopen("output.txt","w",stdout) #define cpp_io() {ios_base::sync_with_stdio(false);cin.tie(NULL);} #define BUFFSIZE 30000 #define INF 10000000000000000LL #define MOD 1000000007 #define MAX 200000 #define pb push_back #define mkpr make_pair #define pii pair<int, int> #define pll pair<ll, ll> #define fi first #define si second typedef long long ll; char CRTBUFF[BUFFSIZE]; #define dbg(args...) {cout<<"-->";debugger::call(#args,args);cout<<"\n";} struct debugger{ static void call(const char* it){} template<typename T, typename ... aT> static void call(const char* it, T a, aT... rest){ string b; for(;*it&&*it!=',';++it) if(*it!=' ')b+=*it; cout<<b<<"="<<a<<" "; call(++it, rest...); } }; /* Template Ends */ int n, m, k; int imp[10]; vector<pii> G[MAX+10]; ll dp[1<<6][MAX+10]; ll D[MAX+10]; void dijkstra(int mask) { priority_queue<pll, vector<pll>, greater<pll> > que; fill(D, D+n, INF); FOR(u, n){ que.push({dp[mask][u], u}); } while(!que.empty()){ ll c=que.top().fi, u=que.top().si; que.pop(); if(c>D[u]) continue; D[u]=c; for(auto it: G[u]){ ll v=it.fi, w=it.si; if(D[u]+w<D[v]){ D[v]=D[u]+w; que.push({D[v], v}); } } } FOR(u, n){ // dbg(mask, u, D[u]); dp[mask][u]=D[u]; } } int main() { //read(); cpp_io(); //begin while(cin >> n >> k >> m){ FOR(i, k) cin >> imp[i]; FOR(i, k) imp[i]--; FOR(i, m){ int u, v, w; cin >> u >> v >> w; u--, v--; G[u].pb({v, w}); G[v].pb({u, w}); } ll lim=1<<k; FOR(mask, lim) FOR(u, n) dp[mask][u]=INF; FOR(i, k) dp[1<<i][imp[i]]=0; FOR(mask, lim){ FOR(u, n){ for(int sm=mask; sm>0; sm=(sm-1)&mask){ dp[mask][u]=min(dp[mask][u], dp[sm][u]+dp[sm^mask][u]); } } dijkstra(mask); } ll ans=INF; FOR(u, n){ ans=min(ans, dp[lim-1][u]); } cout << ans << "\n"; break; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...