Submission #1083072

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1083072	2024-09-02T12:43:08 Z	User0069	Cities (BOI16_cities)	C++17	Compilation error	0 ms	0 KB

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 int INF=1e18;
int n,k,m,imp[maxn],dp[maxn][32],vis[maxn][32],f[maxn][6];
vector<int> adj[maxn];
struct edge
{
    int u,v,w;
}e[2*maxn];
struct ele
{
    int des,mask;
    long long dis;
};
bool operator <(ele a,ele b)
{
    return a.dis>b.dis;
}
priority_queue<ele> pq;
void predijkstra()
{
    for(int i=1;i<=n;i++)
    {
        if(imp[i])
        {
            pq.push({i,imp[i]-1,0});
        }
    }
    while(!pq.empty())
    {
        int des=pq.top().des;
        int dis=pq.top().dis;
        int mask=pq.top().mask;
        pq.pop();
        if(vis[des][mask]) continue;
        f[des][mask]=dis;
        vis[des][mask]=1;
        for(int i:adj[des])
        {
            int des1=e[i].u+e[i].v-des;
            if(!vis[des1][mask])
            pq.push({des1,mask,dis+e[i].w});
        }
    }
}
void dijkstra()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<(1<<k);j++) vis[i][j]=0;
        if(imp[i])
        {
            pq.push({i,0,0});
        }
    }
    while(!pq.empty())
    {
        int des=pq.top().des;
        int dis=pq.top().dis;
        int mask=pq.top().mask;
        pq.pop();
        if(vis[des][mask]) continue;
        dp[des][mask]=dis;
        vis[des][mask]=1;
        for(int i:adj[des])
        {
            int des1=e[i].u+e[i].v-des;
            if(!vis[des1][mask])
            pq.push({des1,mask,dis+e[i].w});
        }
        for(int i=0;i<k;i++)
        {
            if(((1<<i)|mask)!=mask)
            {
                if(!vis[des][mask^(1<<i)])
                {
                    pq.push({des,(1<<i)^mask,dp[des][mask]+f[des][i]});
                }
            }
        }
    }
}
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);
    }
    predijkstra();
    dijkstra();
    long long ans=INF;
    for(int i=1;i<=n;i++)
    {
        if(vis[i][(1<<k)-1]) ans=min(ans,dp[i][(1<<k)-1]);
//        for(int j=0;j<k;j++)
//        {
//            cout<<f[i][j]<<" ";
//        }
//        cout<<"\n";
    }
    cout<<ans;
}

Compilation message

cities.cpp:14:15: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   14 | const int INF=1e18;
      |               ^~~~
cities.cpp: In function 'int main()':
cities.cpp:120:57: error: no matching function for call to 'min(long long int&, int&)'
  120 |         if(vis[i][(1<<k)-1]) ans=min(ans,dp[i][(1<<k)-1]);
      |                                                         ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from cities.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:230:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
  230 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:230:5: note:   template argument deduction/substitution failed:
cities.cpp:120:57: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
  120 |         if(vis[i][(1<<k)-1]) ans=min(ans,dp[i][(1<<k)-1]);
      |                                                         ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from cities.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:278:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
  278 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:278:5: note:   template argument deduction/substitution failed:
cities.cpp:120:57: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
  120 |         if(vis[i][(1<<k)-1]) ans=min(ans,dp[i][(1<<k)-1]);
      |                                                         ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from cities.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3468:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)'
 3468 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3468:5: note:   template argument deduction/substitution failed:
cities.cpp:120:57: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
  120 |         if(vis[i][(1<<k)-1]) ans=min(ans,dp[i][(1<<k)-1]);
      |                                                         ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from cities.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3474:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)'
 3474 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3474:5: note:   template argument deduction/substitution failed:
cities.cpp:120:57: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
  120 |         if(vis[i][(1<<k)-1]) ans=min(ans,dp[i][(1<<k)-1]);
      |                                                         ^
cities.cpp:98:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |         freopen(taskname".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
cities.cpp:99:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |         freopen(taskname".OUT","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~