제출 #1326610

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1326610		SSKMF	Travelling Merchant (APIO17_merchant)	C++20	12 / 100	53 ms	1436 KiB

merchant

#include <bits/stdc++.h>
using namespace std;

pair <int , int> cost[101][1001];
pair <int , int64_t> factor[101][101];
int64_t distanta[101][101];

int main ()
{
    ios :: sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int numar_noduri , numar_muchii , numar_candidati;
    cin >> numar_noduri >> numar_muchii >> numar_candidati;

    for (int nod = 1 ; nod <= numar_noduri ; nod++) {
        for (int indice = 1 ; indice <= numar_candidati ; indice++)
            { cin >> cost[nod][indice].first >> cost[nod][indice].second; }
    }

    for (int nod_1 = 1 ; nod_1 <= numar_noduri ; nod_1++) {
        for (int nod_2 = 1 ; nod_2 <= numar_noduri ; nod_2++)
        {
            factor[nod_1][nod_2].second = 1e18;
            if (nod_1 == nod_2)
                { continue; }

            for (int indice = 1 ; indice <= numar_candidati ; indice++) {
                if (cost[nod_2][indice].second != -1 && cost[nod_1][indice].first != -1)
                    { factor[nod_1][nod_2].first = max(factor[nod_1][nod_2].first , cost[nod_2][indice].second - cost[nod_1][indice].first); }
            }
        }
    }

    while (numar_muchii--)
        { int nod[2]; cin >> nod[0] >> nod[1] >> factor[nod[0]][nod[1]].second; }

    for (int intermediar = 1 ; intermediar <= numar_noduri ; intermediar++) {
        for (int nod_1 = 1 ; nod_1 <= numar_noduri ; nod_1++) {
            for (int nod_2 = 1 ; nod_2 <= numar_noduri ; nod_2++) {
                if (nod_1 != nod_2)
                    { factor[nod_1][nod_2].second = min(factor[nod_1][nod_2].second , factor[nod_1][intermediar].second + factor[intermediar][nod_2].second); }
            }
        }
    }

    int64_t stanga = 1 , dreapta = (int64_t)1e9 + 1;
    while (stanga <= dreapta)
    {
        const int64_t mijloc = (stanga + dreapta) >> 1;
        vector < pair < pair <int , int> , int64_t > > muchii;
        for (int nod_1 = 1 ; nod_1 <= numar_noduri ; nod_1++) {
            for (int nod_2 = 1 ; nod_2 <= numar_noduri ; nod_2++) {
                if (factor[nod_1][nod_2].second != 1e18)
                    { distanta[nod_1][nod_2] = factor[nod_1][nod_2].first - 1LL * mijloc * factor[nod_1][nod_2].second; }
                else
                    { distanta[nod_1][nod_2] = -1e18; }
            }
        }

        for (int intermediar = 1 ; intermediar <= numar_noduri ; intermediar++) {
            for (int nod_1 = 1 ; nod_1 <= numar_noduri ; nod_1++) {
                for (int nod_2 = 1 ; nod_2 <= numar_noduri ; nod_2++)
                    { distanta[nod_1][nod_2] = max(distanta[nod_1][nod_2] , distanta[nod_1][intermediar] + distanta[intermediar][nod_2]); }
            }
        }

        if (distanta[1][1] >= 0) { stanga = mijloc + 1; }
        else { dreapta = mijloc - 1; }
    }

    cout << dreapta;

    return 0;
}

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