Submission #533477

#	Time	Username	Problem	Language	Result	Execution time	Memory
533477		N1NT3NDO	Autobus (COCI22_autobus)	C++14	70 / 70	505 ms	9944 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define sz(x) (int)x.size()
#define fi first
#define sd second
#define all(x) x.begin(), x.end()
//#pragma GCC target ("avx2")
//#pragma GCC optimization ("O3")
//#pragma GCC optimization ("unroll-loops")

using namespace std;
//using namespace __gnu_pbds;

//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

const int N = 75;
//vector< pair<int, int> > g[N];
int n, m, q, k, F;
bool used[N];
ll dst[N][N][N], g[N][N];

/*
void dfs(int v, int skok, ll sum)
{
    if (skok > k || sum > ans) return;

    if (v == F)
    {
        ans = min(ans, sum);
        return;
    }

    for(auto [u, w] : g[v])
    {
        dfs(u, skok + 1, sum + w);
    }
}
*/

void calc(int x)
{
    for(int i = 1; i <= n; i++)
      for(int j = 0; j <= k; j++)
        dst[x][i][j] = 1e18;
    dst[x][x][0] = 0;
    set< pair<ll, pair<int, int> > > se;


    se.insert({0, {0, x}});

    while(sz(se) > 0)
    {
        auto c = *se.begin(); se.erase(se.begin());
        ll d = c.fi;
        int v = c.sd.sd, skok = c.sd.fi;

        if (dst[x][v][skok] < d) continue;

        for(int u = 1; u <= n; u++)
        {
            if (g[v][u] == 1e18) continue;
            ll w = g[v][u];
            if (skok + 1 <= k && dst[x][v][skok] + w < dst[x][u][skok + 1])
            {
                dst[x][u][skok + 1] = dst[x][v][skok] + w;
                se.insert({dst[x][u][skok + 1], {skok + 1, u}});
            }
        }
    }

}

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

    for(int i = 1; i <= n; i++)
      for(int j = 1; j <= n; j++)
        g[i][j] = 1e18;

    for(int i = 1; i <= m; i++)
    {
        int u, v;
        ll z;
        cin >> u >> v >> z;
        g[u][v] = min(g[u][v], z);
    }


    cin >> k >> q;

    k = min(k, n);

    for(int i = 1; i <= n; i++)
      calc(i);

    while(q--)
    {
        int S;
        cin >> S >> F;
        ll ans = 1e18;

        for(int i = 0; i <= k; i++) ans = min(ans, dst[S][F][i]);

        if (ans == 1e18) cout << -1 << '\n';
        else cout << ans << '\n';
    }

}

• Subtask 1: 15 / 15
• Subtask 2: 15 / 15
• Subtask 3: 25 / 25
• Subtask 4: 15 / 15