Submission #361571

#TimeUsernameProblemLanguageResultExecution timeMemory
361571DymoCities (BOI16_cities)C++14
74 / 100
6054 ms149092 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long #define pll pair<ll,ll> #define ff first #define ss second #define pb push_back #define endl "\n" const ll maxn =2e5+10; const ll mod=1e9+7; const ll base=3e16; ll dp[maxn][6]; ll pos[maxn]; ll dp1[maxn][(1ll<<5)]; vector<pll> adj[maxn]; ll n; ll k, m; ll a[maxn]; void dosth(ll u,ll pos) { for (int i=1;i<=n;i++) { dp[i][pos]=base; } dp[u][pos]=0; priority_queue<pll,vector<pll>,greater<pll>> q; q.push(make_pair(dp[u][pos],u)); while (!q.empty()) { auto p=q.top(); q.pop(); ll u=p.ss; if (p.ff!=dp[u][pos]) continue; for (auto t:adj[u]) { ll to=t.ff; ll w=t.ss; if (dp[to][pos]>dp[u][pos]+w) { dp[to][pos]=dp[u][pos]+w; q.push(make_pair(dp[to][pos],to)); } } } } ll dosth1() { priority_queue<pair<ll,pll>,vector<pair<ll,pll>>,greater<pair<ll,pll>>> q; for (int i=1;i<=n;i++) { for (int j=1;j<(1ll<<k);j++) { dp1[i][j]=base; } q.push(make_pair(dp1[i][0],make_pair(i,0))); } while (!q.empty()) { auto p=q.top(); q.pop(); ll u=p.ss.ff; ll t=p.ss.ss; if (dp1[u][t]!=p.ff) continue; for (int j=0;j<k;j++) { if (t&(1ll<<j)) { } else { ll w=dp[u][j]; if (dp1[u][t^(1ll<<j)]>dp1[u][t]+w) { dp1[u][t^(1ll<<j)]=dp1[u][t]+w; q.push(make_pair(dp1[u][t^(1ll<<j)],make_pair(u,t^(1ll<<j)))); } } } for (auto p:adj[u]) { ll to=p.ff; ll w=p.ss; if (dp1[to][t]>dp1[u][t]+w) { dp1[to][t]=dp1[u][t]+w; q.push(make_pair(dp1[to][t],make_pair(to,t))); } } } ll ans=base; for (int i=1;i<=n;i++) { ans=min(ans,dp1[i][(1ll<<k)-1]); } return ans; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); if (fopen("t.inp","r")) { freopen("test.inp","r",stdin); freopen("test.out","w",stdout); } cin>> n>> k>>m ; for (int i=0;i<k;i++) { cin>>a[i]; } for (int i=1;i<=m;i++) { ll x, y, w; cin>> x>> y>> w; adj[x].pb(make_pair(y,w)); adj[y].pb(make_pair(x,w)); } for (int i=0;i<k;i++) { dosth(a[i],i); } cout <<dosth1(); }

Compilation message (stderr)

cities.cpp: In function 'int main()':
cities.cpp:107:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  107 |         freopen("test.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
cities.cpp:108:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  108 |         freopen("test.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
#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...