제출 #1326602

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1326602		SSKMF	여행하는 상인 (APIO17_merchant)	C++20	0 / 100	69 ms	1784 KiB

merchant

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

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

inline void Solve ()
{
    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 = 1e12;
            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 , (int64_t)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++)
                { factor[nod_1][nod_2].second = min(factor[nod_1][nod_2].second , factor[nod_1][intermediar].second + factor[intermediar][nod_2].second); }
        }
    }

    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 == 1e12)
                { factor[nod_1][nod_2].first = 0; }

            if (nod_1 == nod_2)
                { factor[nod_1][nod_2].first = 0; factor[nod_1][nod_2].second = 1e12; }
        }
    }
    
    int64_t stanga = 1 , dreapta = 1e12;
    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++)
        {
            distanta[nod_1] = -1e12;
            for (int nod_2 = 1 ; nod_2 <= numar_noduri ; nod_2++) {
                if (factor[nod_1][nod_2].second != 1e12)
                    { muchii.emplace_back(make_pair(nod_1 , nod_2) , factor[nod_1][nod_2].first - 1LL * mijloc * factor[nod_1][nod_2].second); }
            }
        }

        distanta[1] = 0;
        for (int ramas = numar_noduri - 1 ; ramas ; ramas--) {
            for (auto& muchie : muchii)
                { distanta[muchie.first.second] = max(distanta[muchie.first.second] , distanta[muchie.first.first] + muchie.second); }
        }

        bool gasit = false;
        for (auto& muchie : muchii) {
            if (muchie.first.second == 1 && distanta[muchie.first.first] + muchie.second >= 0)
                { gasit = true; break; }
        }

        if (gasit) { stanga = mijloc + 1; }
        else { dreapta = mijloc - 1; }
    }

    cout << dreapta;
}

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

    int numar_teste = 1;
    // cin >> numar_teste;
    while (numar_teste--)
        { Solve(); }

    return 0;
}

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