oj.uz

Submission #696640

# Submission time Handle Problem Language Result Execution time Memory
696640 2023-02-07T02:34:09 Z Hiennoob123 Autobus (COCI22_autobus) C++14
70 / 70
 324 ms 17564 KB 
#include <bits/stdc++.h>
#define ll long long
#define pll pair<ll,ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
const ll maxn = 71*71+10;
const ll add = 1e5;
ll n, m;
vector<pair<ll,ll>> T[80];
ll dis[71][71][80];
bool chk[71][71][80];
vector<pair<pll,ll>> road;
void solve_this(ll v)
{
    //cout << v << "\n";
    for(int i = 1; i<= n; i++)
    {
        //if(v==70) cout << i << " ";
        for(int j = 0; j<= 71; j++)
        {
            dis[v][i][j] = LLONG_MAX;
            //if(v==70&&i==69) cout << dis[v][i][j] << "-\n";
            chk[v][i][j] = 0;
        }
    }
    dis[v][v][0] = 0;
    chk[v][v][0] = 1;
    //cout << dis[70][69][71] << " " << v << "-\n";
    ll tong = 0;
    for(int j = 1; j<= 71; j++)
    {
        for(int i = 1; i<= n; i++)
        {
            //cout << i << " " << j << "\n";
            if(!chk[v][i][j-1]) continue;
            for(auto u: T[i])
            {
                tong++;
                chk[v][u.fi][j] = 1;
                dis[v][u.fi][j] = min(dis[v][u.fi][j], dis[v][i][j-1]+u.se);
                //if(v==70&&dis[v][i][j]==0&&i!=v)
                //{
                    //cout << u.se << "\n";
                    //cout << u.fi << " " << dis[v][i][j] << " " << j << " " << i << "\n";
                //}
            }
        }
    }
    //cout << dis[70][69][71] << " " << v << "\n";
}
void solve()
{
    cin >> n >> m;
    for(int i = 0; i< m; i++)
    {
        ll a, b, c; cin >> a >> b >> c;
        road.push_back(mp(mp(a, b), c));
    }
    sort(road.begin(), road.end());
    for(int i = 1; i<= n; i++)
    {
        T[i].push_back(mp(i, 0));
    }
    for(int i = 0; i< m; i++)
    {
        if(i==0)
        {
            //cout << road[i].se<< "\n";
            T[road[i].fi.fi].push_back(mp(road[i].fi.se,road[i].se));
            continue;
        }
        if(road[i].fi==road[i-1].fi) continue;
        else
        {
            //cout << road[i].se<< "\n";
            T[road[i].fi.fi].push_back(mp(road[i].fi.se,road[i].se));
        }
    }
    for(int i = 1; i <= n; i++) solve_this(i);
    ll k, q;
    cin >> k >> q;
    k = min(k, (ll)71);
    for(int i = 0; i< q; i++)
    {
        ll a, b; cin >> a >> b;
        //if(a==1) cout << a << " " << b << " " << dis[a][b][k] << "\n"
        //if(dis[a][b][k]==0) cout << a << " " << b << "\n";
        if(dis[a][b][k]==LLONG_MAX) cout << -1;
        else cout << dis[a][b][k];
        cout << "\n";
    }
}
int main()
{
    ios_base::sync_with_stdio(NULL) ; cin.tie(nullptr) ; cout.tie(nullptr);
    //freopen("B.inp","r",stdin);
    ll test_case = 1;
    while(test_case--)
    {
        solve();
    }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 328 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 3884 KB Output is correct
2 Correct 14 ms 3864 KB Output is correct
3 Correct 14 ms 3924 KB Output is correct
4 Correct 29 ms 3920 KB Output is correct
5 Correct 31 ms 3920 KB Output is correct
6 Correct 80 ms 4052 KB Output is correct
7 Correct 74 ms 4064 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 328 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 15 ms 3824 KB Output is correct
8 Correct 14 ms 3932 KB Output is correct
9 Correct 30 ms 3920 KB Output is correct
10 Correct 29 ms 3892 KB Output is correct
11 Correct 75 ms 4084 KB Output is correct
12 Correct 77 ms 4048 KB Output is correct
13 Correct 268 ms 16028 KB Output is correct
14 Correct 252 ms 16084 KB Output is correct
15 Correct 267 ms 16036 KB Output is correct
16 Correct 268 ms 16252 KB Output is correct
17 Correct 266 ms 16252 KB Output is correct
18 Correct 265 ms 16228 KB Output is correct
19 Correct 259 ms 16268 KB Output is correct
20 Correct 261 ms 16264 KB Output is correct
21 Correct 263 ms 16220 KB Output is correct
22 Correct 264 ms 16316 KB Output is correct
23 Correct 261 ms 16180 KB Output is correct
24 Correct 279 ms 16456 KB Output is correct
25 Correct 268 ms 16524 KB Output is correct
26 Correct 267 ms 16628 KB Output is correct
27 Correct 265 ms 16688 KB Output is correct
28 Correct 284 ms 16480 KB Output is correct
29 Correct 260 ms 16032 KB Output is correct
30 Correct 264 ms 16092 KB Output is correct
31 Correct 259 ms 16100 KB Output is correct
32 Correct 239 ms 15980 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 328 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 15 ms 3884 KB Output is correct
8 Correct 14 ms 3864 KB Output is correct
9 Correct 14 ms 3924 KB Output is correct
10 Correct 29 ms 3920 KB Output is correct
11 Correct 31 ms 3920 KB Output is correct
12 Correct 80 ms 4052 KB Output is correct
13 Correct 74 ms 4064 KB Output is correct
14 Correct 15 ms 3824 KB Output is correct
15 Correct 14 ms 3932 KB Output is correct
16 Correct 30 ms 3920 KB Output is correct
17 Correct 29 ms 3892 KB Output is correct
18 Correct 75 ms 4084 KB Output is correct
19 Correct 77 ms 4048 KB Output is correct
20 Correct 268 ms 16028 KB Output is correct
21 Correct 252 ms 16084 KB Output is correct
22 Correct 267 ms 16036 KB Output is correct
23 Correct 268 ms 16252 KB Output is correct
24 Correct 266 ms 16252 KB Output is correct
25 Correct 265 ms 16228 KB Output is correct
26 Correct 259 ms 16268 KB Output is correct
27 Correct 261 ms 16264 KB Output is correct
28 Correct 263 ms 16220 KB Output is correct
29 Correct 264 ms 16316 KB Output is correct
30 Correct 261 ms 16180 KB Output is correct
31 Correct 279 ms 16456 KB Output is correct
32 Correct 268 ms 16524 KB Output is correct
33 Correct 267 ms 16628 KB Output is correct
34 Correct 265 ms 16688 KB Output is correct
35 Correct 284 ms 16480 KB Output is correct
36 Correct 260 ms 16032 KB Output is correct
37 Correct 264 ms 16092 KB Output is correct
38 Correct 259 ms 16100 KB Output is correct
39 Correct 239 ms 15980 KB Output is correct
40 Correct 14 ms 3848 KB Output is correct
41 Correct 13 ms 3924 KB Output is correct
42 Correct 27 ms 3948 KB Output is correct
43 Correct 27 ms 3848 KB Output is correct
44 Correct 76 ms 4120 KB Output is correct
45 Correct 75 ms 4080 KB Output is correct
46 Correct 252 ms 16084 KB Output is correct
47 Correct 284 ms 16008 KB Output is correct
48 Correct 259 ms 15972 KB Output is correct
49 Correct 265 ms 15996 KB Output is correct
50 Correct 265 ms 16112 KB Output is correct
51 Correct 279 ms 16224 KB Output is correct
52 Correct 295 ms 16112 KB Output is correct
53 Correct 282 ms 16272 KB Output is correct
54 Correct 276 ms 16208 KB Output is correct
55 Correct 274 ms 16700 KB Output is correct
56 Correct 324 ms 17108 KB Output is correct
57 Correct 273 ms 17048 KB Output is correct
58 Correct 318 ms 17400 KB Output is correct
59 Correct 313 ms 17492 KB Output is correct
60 Correct 308 ms 17440 KB Output is correct
61 Correct 297 ms 17564 KB Output is correct
62 Correct 277 ms 16860 KB Output is correct
63 Correct 272 ms 16968 KB Output is correct
64 Correct 270 ms 16940 KB Output is correct
65 Correct 280 ms 16968 KB Output is correct