Submission #734471

#	Time	Username	Problem	Language	Result	Execution time	Memory
734471		bgnbvnbv	Travelling Merchant (APIO17_merchant)	C++14	100 / 100	127 ms	4460 KiB

merchant

#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<ll,ll>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=2e5;
const ll inf=1e18;
const ll mod=1e9+7;
ll n;
ll d[101][101],c[101][101],dis[101][101];
bool check(ll mid)
{
    //sum(v)>=mid*sum(w)
    ll x;
    vector<ll>dd(n+1);
    for(int i=1;i<=n;i++)
    {
        x=-1;
        for(int j=1;j<=n;j++)
        {
            for(int q=1;q<=n;q++)
            {
                if(j!=q&&d[j][q]!=inf)
                {
                    ll w=-1*(c[j][q]-d[j][q]*mid);
                    if(dd[q]>dd[j]+w)
                    {
                        dd[q]=dd[j]+w;
                        if(i==n) return true;
                    }
                }
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            dis[i][j]=inf;
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(i!=j&&d[i][j]!=inf)
            {
                dis[i][j]=-(c[i][j]-mid*d[i][j]);
            }
        }
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            for (int t = 1; t <= n; ++t) {
                if(dis[j][t]>dis[j][i]+dis[i][t])
                {
                    dis[j][t]=dis[j][i]+dis[i][t];
                }
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        //cout << dis[i][i]<<' ';
        if(dis[i][i]<=0) return true;
    }
    return false;
}
ll m,k;
bool vis[101];
vector<pli>g[101];

void dij(ll s)
{
    for(int i=1;i<=n;i++) d[s][i]=inf,vis[i]=false;
    d[s][s]=0;
    priority_queue<pli,vector<pli>,greater<pli>>pq;
    pq.push({d[s][s],s});
    while(!pq.empty())
    {
        ll u=pq.top().se;
        pq.pop();
        if(vis[u]==true) continue;
        vis[u]=true;
        for(auto zz:g[u])
        {
            if(d[s][zz.fi]>d[s][u]+zz.se)
            {
                d[s][zz.fi]=d[s][u]+zz.se;
                pq.push({d[s][zz.fi],zz.fi});
            }
        }
    }
}
ll b[101][1001],s[101][1001];

void solve()
{
    cin >> n >> m >> k;
    for(int i=1;i<=n;i++)
    {

        for(int j=1;j<=k;j++) cin >> b[i][j]>> s[i][j];
        b[i][0]=s[i][0]=0;
    }
    for(int i=1;i<=m;i++)
    {
        ll u,v,w;
        cin >> u >> v >> w;
        g[u].pb({v,w});
    }
    for(int i=1;i<=n;i++)
    {
        dij(i);
    }
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) c[i][j]=0;
    for(int i=1;i<=k;i++)
    {
        for(int j=1;j<=n;j++)
        {
            for(int q=1;q<=n;q++)
            {
                if(j!=q&&b[j][i]!=-1&&s[q][i]!=-1)
                {
                    c[j][q]=max(c[j][q],s[q][i]-b[j][i]);
                }
            }
        }
    }
    ll low=0,high=1e9+10;
    while(low<=high)
    {
        ll mid=low+high>>1;
        if(check(mid)) low=mid+1;
        else high=mid-1;
    }
    cout << high;
}
int main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}

Compilation message (stderr)

merchant.cpp: In function 'bool check(ll)':
merchant.cpp:18:8: warning: variable 'x' set but not used [-Wunused-but-set-variable]
   18 |     ll x;
      |        ^
merchant.cpp: In function 'void solve()':
merchant.cpp:137:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  137 |         ll mid=low+high>>1;
      |                ~~~^~~~~

• Subtask 1: 12 / 12
• Subtask 2: 21 / 21
• Subtask 3: 33 / 33
• Subtask 4: 34 / 34