Submission #647657

#	Time	Username	Problem	Language	Result	Execution time	Memory
647657		Sara_smd	Travelling Merchant (APIO17_merchant)	C++14	100 / 100	104 ms	2340 KiB

merchant

//Khoda Hast :)//
#include<bits/stdc++.h>
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define ret(x) return cout << x << endl, 0;
#define all(x) x.begin(),x.end()
#define pf push_front
#define ff pop_front
#define pb push_back
#define bb pop_back
#define F first
#define S second
using namespace std;
const int N = 200, M = 1e4, T = 1e3 + 10, OO = 1e9;
int a[N][T], b[N][T], l[N][N], p[N][N], n, m, t;
long long d[N][N];
vector<int> adj[N];
bool check(int x)
{
    bool is = false;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            d[i][j] = 1ll * l[i][j] * x - 1ll * p[i][j];
    for(int k = 0; k < n; k++)
        for(int i = 0; i < n; i++)
            for(int  j = 0; j < n; j++)
            {
                if(i == j && i != k && d[i][k] + d[k][j] <= 0)
                    is = true;
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
    return is;
}
int main()
{
    ios;
    cin >> n >> m >> t;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < t; j++)
            cin >> a[i][j] >> b[i][j];
    for(int i = 0; i < m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        u--, v--;
        adj[u].pb(v);
        d[u][v] = w;
    }
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            if(i != j && !d[i][j])
                d[i][j] = 1ll * OO;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            l[i][j] = OO;
    for(int i = 0; i < n; i++)
    {
        l[i][i] = 0;
        for(auto j : adj[i])
            l[i][j] = d[i][j];
    }
    for(int k = 0; k < n; k++)
        for(int i = 0; i < n; i++)
            for(int  j = 0; j < n; j++)
                l[i][j] = min(l[i][j], l[i][k] + l[k][j]);
    for(int i = 0; i < n; i++)
        adj[i].clear();
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
        {
            bool is = false;
            for(int k = 0; k < t; k++)
                if(a[i][k] != -1 && b[j][k] != -1)
                    p[i][j] = max(p[i][j], b[j][k] - a[i][k]), is = true;
            if(is)
                adj[i].pb(j);
        }
    int lft = 0, rgt = OO;
    while(lft + 1 < rgt)
    {
        int mid = (lft + rgt) / 2;
        if(check(mid))
            lft = mid;
        else
            rgt = mid;
    }
    cout << lft << endl;
    return 0;
}

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