제출 #696683

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
696683		tranxuanbach	Autobus (COCI22_autobus)	C++17	70 / 70	141 ms	4920 KiB

Main

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

#define endl '\n'
#define fi first
#define se second
#define For(i, l, r) for (auto i = (l); i < (r); i++)
#define ForE(i, l, r) for (auto i = (l); i <= (r); i++)
#define FordE(i, l, r) for (auto i = (l); i >= (r); i--)
#define Fora(v, a) for (auto v: (a))
#define bend(a) (a).begin(), (a).end()
#define isz(a) ((signed)(a).size())

using ll = long long;
using ld = long double;
using pii = pair <int, int>;
using vi = vector <int>;
using vpii = vector <pii>;
using vvi = vector <vi>;

const int N = 70 + 5, inf = 1e9 + 7;

int n, m;
int adj[N][N];

int dp[N][N][N];

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("KEK.inp", "r", stdin);
    // freopen("KEK.out", "w", stdout);
    cin >> n >> m;
    ForE(u, 1, n){
        ForE(v, 1, n){
            adj[u][v] = inf;
        }
    }
    while (m--){
        int u, v, w; cin >> u >> v >> w;
        adj[u][v] = min(adj[u][v], w);
    }

    int k, q; cin >> k >> q; k = min(k, n);
    ForE(u, 1, n){
        ForE(v, 1, n){
            dp[0][u][v] = (u == v ? 0 : inf);
        }
    }
    ForE(i, 1, k){
        ForE(u, 1, n){
            ForE(v, 1, n){
                dp[i][u][v] = (u == v ? 0 : inf);
            }
        }
        ForE(w, 1, n){
            ForE(u, 1, n){
                ForE(v, 1, n){
                    dp[i][u][v] = min(dp[i][u][v], dp[i - 1][u][w] + adj[w][v]);
                }
            }
        }
    }
    while (q--){
        int u, v; cin >> u >> v;
        cout << (dp[k][u][v] == inf ? -1 : dp[k][u][v]) << endl;
    }
}

/*
==================================================+
INPUT                                             |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
OUTPUT                                            |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
*/

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