Submission #1337286

#	Time	Username	Problem	Language	Result	Execution time	Memory
1337286		diana	Factories (JOI14_factories)	C++20	0 / 100	5038 ms	204636 KiB

factories

#include "factories.h"
#define fi first
#define se second
#define ll long long
#define pii pair<ll, ll>
#include <bits/stdc++.h>
using namespace std;

const int M = 5e3+3, R=1e17;
int n;
vector<pii> graf[M];
ll dist[M][M];

void dijkstra(int v)
{
    for(int i=0; i<n; i++)  dist[v][i] = R;
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    dist[v][v] = 0;
    pq.push({0, v});
    bool vis[n]{};
    while(!pq.empty())
    {
        pii p = pq.top(); pq.pop();
        if(vis[p.se]) continue;
        vis[p.se] = 1;
        for(auto x: graf[p.se])
            if(x.se + p.fi < dist[v][x.fi])
            {
                dist[v][x.fi] = x.se + p.fi;
                pq.push({dist[v][x.fi], x.fi});
            }
    }
}

void Init(int N, int A[], int B[], int D[]) {
    n = N;
    for(int i=0; i<N; i++)
        graf[A[i]].push_back({B[i], D[i]}),
        graf[B[i]].push_back({A[i], D[i]});
    for(int i=0; i<N; i++)
        dijkstra(i);
}

long long Query(int S, int X[], int T, int Y[]) {
    ll mn = R;
    for(int i=0; i<S; i++)
        for(int j=0; j<T; j++)
            mn = min(mn, dist[X[i]][Y[j]]);

    return mn;
}

Compilation message (stderr)

factories.cpp:9:24: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+17' to '2147483647' [-Woverflow]
    9 | const int M = 5e3+3, R=1e17;
      |                        ^~~~

• Subtask 1: 0 / 15
• Subtask 2: 0 / 18
• Subtask 3: 0 / 67