Submission #1315011

#	Time	Username	Problem	Language	Result	Execution time	Memory
1315011		huypham2009	Cities (BOI16_cities)	C++20	Compilation error	0 ms	0 KiB

cities

#include <bits/stdc++.h>
using namespace std;
// #define int long long
const int maxn=1e5+5;
const long long inf=1e18;
int n,m,k,imcity[10];
long long dp[35][maxn];
vector<pair<int,int>>g[maxn];
int MASK(int x)
{
    return 1<<x;
}
int fullmask(int x)
{
    return (1<<x)-1;
}
int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    // freopen("cities.inp","r",stdin);    freopen("cities.out","w",stdout);
    cin>>n>>k>>m;
    for(int i=1;i<=k;i++)   cin>>imcity[i];
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        g[u].push_back({v,w});
        g[v].push_back({u,w});
    }
    for(int i=1;i<=fullmask(k);i++)
    {
        for(int j=1;j<=n;j++)
        {
            dp[i][j]=inf;
        }
    }
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
    for(int i=1;i<=k;i++)
    {
        int curmask=MASK(i-1);
        dp[curmask][imcity[i]]=0;
        pq.push({0,imcity[i]});
        while(pq.size())
        {
            pair<int,int>res=pq.top();
            pq.pop();
            int u=res.second,w=res.first;
            if(w>dp[curmask][u])    continue;
            for(pair<int,int> v:g[u])
            {
                if(dp[curmask][v.first]>w+v.second)
                {
                    dp[curmask][v.first]=w+v.second;
                    pq.push({dp[curmask][v.first],v.first});
                }
            }
        }
    }
//    cout<<MASK(k);
    for(int mask=1;mask<MASK(k);mask++)
    {
        long long hi=inf;
        for(int submask=mask;submask>0;submask=(submask-1)&mask)
        {
            int other=mask^submask;
            if(submask<other)   break;
            for(int j=1;j<=n;j++)
            {
                if(dp[submask][j]+dp[other][j]<dp[mask][j])
                {
                    dp[mask][j]=dp[submask][j]+dp[other][j];
                    hi=min(hi,dp[mask][j]);
                }
            }
        }
        for(int j=1;j<=n;j++)
        {
            if(dp[mask][j]!=inf&&dp[mask][j]-hi<=10000)
            {
                pq.push({dp[mask][j],j});
            }
        }
        while(pq.size())
        {
            pair<int,int>res=pq.top();
            pq.pop();
            int u=res.second,w=res.first;
            if(w>dp[mask][u])    continue;
            for(pair<int,int> v:g[u])
            {
                if(dp[mask][v.first]>w+v.second)
                {
                    dp[mask][v.first]=w+v.second;
                    pq.push({dp[mask][v.first],v.first});
                }
            }
        }
    }
    int ans=inf;
    for(int i=1;i<=n;i++)
    {
//        cout<<dp[fullmask(k)][i]<<' ';
        ans=min(ans,dp[fullmask(k)][i]);
    }
    cout<<ans;
    return 0;
}

Compilation message (stderr)

cities.cpp: In function 'int32_t main()':
cities.cpp:100:13: warning: overflow in conversion from 'long long int' to 'int' changes value from '1000000000000000000' to '-1486618624' [-Woverflow]
  100 |     int ans=inf;
      |             ^~~
cities.cpp:104:16: error: no matching function for call to 'min(int&, long long int&)'
  104 |         ans=min(ans,dp[fullmask(k)][i]);
      |             ~~~^~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/13/algorithm:60,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51,
                 from cities.cpp:1:
/usr/include/c++/13/bits/stl_algobase.h:233:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
  233 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/13/bits/stl_algobase.h:233:5: note:   template argument deduction/substitution failed:
cities.cpp:104:16: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
  104 |         ans=min(ans,dp[fullmask(k)][i]);
      |             ~~~^~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algobase.h:281:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
  281 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/13/bits/stl_algobase.h:281:5: note:   template argument deduction/substitution failed:
cities.cpp:104:16: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
  104 |         ans=min(ans,dp[fullmask(k)][i]);
      |             ~~~^~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/13/algorithm:61:
/usr/include/c++/13/bits/stl_algo.h:5775:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(initializer_list<_Tp>)'
 5775 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/13/bits/stl_algo.h:5775:5: note:   template argument deduction/substitution failed:
cities.cpp:104:16: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  104 |         ans=min(ans,dp[fullmask(k)][i]);
      |             ~~~^~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algo.h:5785:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(initializer_list<_Tp>, _Compare)'
 5785 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/13/bits/stl_algo.h:5785:5: note:   template argument deduction/substitution failed:
cities.cpp:104:16: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  104 |         ans=min(ans,dp[fullmask(k)][i]);
      |             ~~~^~~~~~~~~~~~~~~~~~~~~~~~