Submission #1083083

#	Time	Username	Problem	Language	Result	Execution time	Memory
1083083		User0069	Cities (BOI16_cities)	C++17	100 / 100	1923 ms	43204 KiB

cities

#include<bits/stdc++.h>
#define taskname ""
#define el '\n'
#define fi first
#define sc second
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
//#define int long long
using namespace std;
#define Faster ios_base::sync_with_stdio(false);cin.tie(0);
const int maxn=1e5+33;
const int N=1e5;
const int mod=1e9+7;
const long long INF=1e18;
int n,k,m,imp[maxn],vis[maxn];
long long dp[maxn][32];
vector<int> adj[maxn];
struct edge
{
    int u,v,w;
} e[2*maxn];
struct ele
{
    int des;
    long long dis;
};
bool operator <(ele a,ele b)
{
    return a.dis>b.dis;
}
priority_queue<ele> pq;
void dijkstra()
{
    for(int i=1;i<(1<<k);i++)
    {
        for(int j=1;j<=n;j++)
        {
            for(int s=1;s<(1<<k);s++)
            {
                if((s|i)==i)
                dp[j][i]=min(dp[j][i^s]+dp[j][s],dp[j][i]);
            }
            vis[j]=0;
            pq.push({j,dp[j][i]});
        }
        while(!pq.empty())
        {
            int des=pq.top().des;
            long long dis=pq.top().dis;
            pq.pop();
            if(vis[des]) continue;
            dp[des][i]=dis;
            vis[des]=1;
            for(int i:adj[des])
            {
                int des1=e[i].u+e[i].v-des;
                if(!vis[des1])
                pq.push({des1,dis+e[i].w});
            }
        }
    }
}
signed main()
{
    if (fopen(taskname".INP","r"))
    {
        freopen(taskname".INP","r",stdin);
        freopen(taskname".OUT","w",stdout);
    }
    Faster
    cin>>n>>k>>m;
    for(int i=1; i<=k; i++)
    {
        int x;
        cin>>x;
        imp[x]=i;
    }
    for(int i=1; i<=m; i++)
    {
        cin>>e[i].u>>e[i].v>>e[i].w;
        adj[e[i].u].push_back(i);
        adj[e[i].v].push_back(i);
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<(1<<k);j++)
        {
            dp[i][j]=INF;
        }
        if(imp[i]) dp[i][1<<(imp[i]-1)]=0;
    }
    dijkstra();
    long long ans=INF;
    for(int i=1;i<=n;i++)
    {
        ans=min(ans,dp[i][(1<<k)-1]);
    }
    cout<<ans;
}

Compilation message (stderr)

cities.cpp: In function 'int main()':
cities.cpp:67:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |         freopen(taskname".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
cities.cpp:68:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |         freopen(taskname".OUT","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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