Submission #166471

#	Time	Username	Problem	Language	Result	Execution time	Memory
166471		combi1k1	Travelling Merchant (APIO17_merchant)	C++14	0 / 100	77 ms	1316 KiB

merchant

#include<bits/stdc++.h>

using namespace std;

#define ll  long long

int s[101][1000];
int b[101][1000];
int d[101][101];
int w[101][101];

int main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n;  cin >> n;
    int m;  cin >> m;
    int k;  cin >> k;

    for(int i = 0 ; i < n ; ++i)
    for(int j = 0 ; j < k ; ++j)
        cin >> b[i][j],
        cin >> s[i][j];

    memset(d,0x3f,sizeof d);

    for(int i = 0 ; i < n ; ++i)    d[i][i] = 0;
    for(int i = 0 ; i < m ; ++i)    {
        int x;  cin >> x;   --x;
        int y;  cin >> y;   --y;
        int t;  cin >> t;
        d[x][y] = t;
        d[y][x] = t;
    }

    for(int T = 0 ; T < n ; ++T)
    for(int i = 0 ; i < n ; ++i)
    for(int j = 0 ; j < n ; ++j)
        d[i][j] = min(d[i][j],d[i][T] + d[T][j]);

    for(int P = 0 ; P < k ; ++P)
    for(int i = 0 ; i < n ; ++i)
    for(int j = 0 ; j < n ; ++j)    if (b[i][P] >= 0 && s[j][P] >= 0)
        w[i][j] = max(w[i][j],s[j][P] - b[i][P]);

    vector<vector<ll> > dd(n,vector<ll>(n));

    int l = 0;
    int r = 1e9 + 7;

    for(; l < r ;)  {
        m = (l + r + 2) / 2;
        for(int i = 0 ; i < n ; ++i)
        for(int j = 0 ; j < n ; ++j)
            dd[i][j] = 1ll * m * d[i][j] - w[i][j];

        for(int T = 0 ; T < n ; ++T)
        for(int i = 0 ; i < n ; ++i)
        for(int j = 0 ; j < n ; ++j)
            dd[i][j] = min(dd[i][j],dd[i][T] + dd[T][j]);

        bool ok = 0;

        for(int i = 0 ; i < n ; ++i)
            if (dd[i][i] <= 0)  {
                ok = 1;
                break;
            }
        if (ok) l = m;
        else    r = m - 1;
    }
    cout << l << endl;
}
/*
4 5 2
10 9 5 2
6 4 20 15
9 7 10 9
-1 -1 16 11
1 2 3
2 3 3
1 4 1
4 3 1
3 1 1
*/

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