제출 #1225719

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1225719		Dreamy_lovesper	Autobus (COCI22_autobus)	C++20	30 / 70	20 ms	7492 KiB

Main

#include <bits/stdc++.h>

using namespace std;

// Do you think you'll ever remember me someday, or will I just fade away from your memory?
#define LIFESUCK ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long
#define str string
#define mll map<ll, ll>
#define vll vector<ll>
#define pll pair<ll, ll>
#define fi first 
#define se second 
#define all(c) c.begin(), c.end()
#define pb push_back
#define debug cout << "I Love You\n";
#define fu(i, a, b) for (int i = a; i <= b; i++)
#define fd(i, b, a) for (int i = b; i >= a; i--)
#define Bitc(msk, j) ((msk >> j) & 1)
#define _log(x) 31 - __builtin_clz(x)

const ll Mod = 1e9 + 7;
const ll inf = (1ll << 30);
const ll lnf = (1ll << 60);

// When time passes and things change... will you still remember someone like me?
int64_t add(ll &a, ll b) {
    a += b;
    if (a >= Mod) a %= Mod;
    while (a < 0) a += Mod;
    return a;
}
int64_t mul(ll a, ll b) {
    a = 1ll * a * b % Mod;
    return a;
}

template <class X, class Y>
bool minimize(X &x, Y y) {
    X eps = 1e-9;
    if (x > y + eps) {
        x = y;
        return 1;
    }
    return 0;
}

template <class X, class Y>
bool maximize(X &x, Y y) {
    X eps = 1e-9;
    if (x + eps < y) {
        x = y;
        return 1;
    }
    return 0;
}

// I wonder… will I just become a distant memory to you one day?
#define mxn 1'00'007
#define maxN 77
ll n, m, k, q;
vector<pll> graph[mxn];

struct Edge {
    ll u, v, w;
} edge[mxn];

struct Quest {
    ll s, t;
} Qu[maxN*maxN];

namespace Love1 {
    bool check () {
        return (n <= 7);
    }

    ll sad = 0;
    ll vis[mxn];

    void dfs(ll u, ll time, ll sum, ll end) {
        if(u == end) {
            if(time <= k) minimize(sad, sum);
            return;
        }
        vis[u] = 1;
        for(auto&[v, w]: graph[u]) {
            if(vis[v]) continue;
            dfs(v, time + 1, sum + w, end);
        }
        vis[u] = 0;
    }

    void DreamyLove () {

        fu(qst, 1, q) {
            auto[s, t] = Qu[qst];
            sad = lnf;
            fu(i, 1, n) vis[i] = 0;
            dfs(s, 0, 0, t);
            if(sad >= lnf) cout << -1 << '\n';
            else cout << sad << '\n';
        }

        //
    }
}

namespace LoveLast {

    ll f[maxN][maxN][maxN];
    ll dist[maxN][maxN];

    void DreamyLove () {
        memset(f, 0x3f, sizeof(f));
        fu(i, 1, n) fu(j, 1, n) f[0][i][j] = (i == j? 0: lnf);
        memset(dist, 0x3f, sizeof(dist));
        fu(i, 1, m) {
            auto[u, v, w] = edge[i];
            minimize(dist[u][v], w); dist[u][u] = 0; dist[v][v] = 0;
        }

        fu(j, 1, min(k, n)) fu(x, 1, n)
            fu(u, 1, n) fu(v, 1, n) minimize(f[j][u][v], f[j - 1][u][x] + dist[x][v]);

        fu(qst, 1, q) {
            auto[s, t] = Qu[qst];
            ll sad = f[k][s][t];
            cout << (sad >=lnf? -1: sad) << '\n';
        }

        //
    }
}

void lovesper(const ll &TestCase) {
    
    cin >> n >> m;
    fu(i, 1, m) {
        ll u, v, w; cin >> u >> v >> w;
        graph[u].pb({v, w});
        edge[i] = {u, v, w};
    }

    cin >> k >> q;
    fu(i, 1, q) {
        ll s, t; cin >> s >> t;
        Qu[i] = {s, t};
    }

    // if(Love1::check()) {
    //     Love1::DreamyLove();
    //     return;
    // }

    LoveLast::DreamyLove();

}

signed main() {
    LIFESUCK

    #define name "lovesper"
    // freopen(name".inp", "r", stdin);
    // freopen(name".out", "w", stdout);
    
    ll Test = 1;
    // cin >> Test;

    fu(i, 1, Test) {
        lovesper(i);
        if (i < Test) cout << '\n';
    }

    return 0;
}

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