제출 #696640

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
696640		Hiennoob123	Autobus (COCI22_autobus)	C++14	70 / 70	324 ms	17564 KiB

Main

#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 / 15
• Subtask 2: 15 / 15
• Subtask 3: 25 / 25
• Subtask 4: 15 / 15