Submission #1117146

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117146		mmk	Travelling Merchant (APIO17_merchant)	C++14	0 / 100	12 ms	1872 KiB

merchant

#include<bits/stdc++.h>
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;

const int MAXN = 1e2 + 10;
const int MAXK = 1e3 + 10;

int compra[MAXN][MAXK], venda[MAXN][MAXK];
int dist[MAXN][2];
vector<int> grafo[MAXN][2], weight[MAXN][2];

void djikstra(int N, int type)
{
    set<pair<int,int>> s;

    for(int i = 2; i <= N; i++)
    {
        dist[i][type] = INF;
    }

    dist[1][type] = 0;
    s.insert({dist[1][type],1});
    while(!s.empty())
    {
        int cur = s.begin() -> second;
        s.erase(s.begin());

        for(int i = 0; i < grafo[cur][type].size(); i++)
        {
            int viz = grafo[cur][type][i];
            int w = weight[cur][type][i];

            if(dist[viz][type] > dist[cur][type] + w)
            {
                s.erase({dist[viz][type],viz});
                dist[viz][type] = dist[cur][type] + w;
                s.insert({dist[viz][type],viz});
            }
        }
    }
}

int32_t main()
{
    cin.tie(0)->sync_with_stdio(0);

    int N,M,K; cin >> N >> M >> K;

    for(int i = 1; i <= N; i++)
    {
        for(int j = 1; j <= 2*K; j++)
        {
            // int x; cin >> x;
            if(j%2 == 1) cin >> compra[i][j];
            else cin >> venda[i][j];
        }
    }

    for(int i = 1; i <= M; i++)
    {
        int a,b,w; cin >> a >> b >> w;

        grafo[a][0].push_back(b);
        weight[a][0].push_back(w);

        grafo[b][1].push_back(a);
        weight[b][1].push_back(w);
    }

    djikstra(N,0);
    djikstra(N,1);

    int resp = 0;

    dist[1][0] = INF;
    for(int i = 0; i < grafo[1][1].size(); i++)
    {
        int viz = grafo[1][1][i];
        int w = weight[1][1][i];

        dist[1][0] = min(dist[1][0],dist[viz][0] + w);
    }

    for(int i = 1; i <= N; i++)
    {
        int tamCiclo = dist[i][0] + dist[i][1];
        for(int prod = 1; prod <= K; prod++)
        {
            int lucro = venda[i][prod] - compra[1][prod];
            resp = max(resp,lucro/tamCiclo);
        }
    }

    cout << resp << "\n";
}

Compilation message (stderr)

merchant.cpp: In function 'void djikstra(long long int, long long int)':
merchant.cpp:29:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |         for(int i = 0; i < grafo[cur][type].size(); i++)
      |                        ~~^~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp: In function 'int32_t main()':
merchant.cpp:77:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     for(int i = 0; i < grafo[1][1].size(); i++)
      |                    ~~^~~~~~~~~~~~~~~~~~~~

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