oj.uz

Submission #526935

# Submission time Handle Problem Language Result Execution time Memory
526935 2022-02-16T16:50:20 Z oneloveforever Autobus (COCI22_autobus) C++14
30 / 70
 1000 ms 492 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define x first
#define y second
#define ii pair<ll,ll>
const ll inf=1e16+7;
vector<vector<ii> >a;
ll n,m;
struct node
{
    ll x,used,value;
    node(ll _value=0,ll _x=0,ll _used=0)
    {
        x=_x,used=_used,value=_value;
    }
};
bool minimize(ll &a,ll b)
{
    if(a>b)
    {
        a=b;
        return true;
    }
    return false;
}
int main()
{
    //freopen("test.inp","r",stdin);
    //freopen("test.out","w",stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    a.resize(n+7);
    for(ll i=1;i<=m;i++)
    {
        ll x,y,value;
        cin>>x>>y>>value;
        a[x].push_back({y,value});
    }
    ll q,k;
    cin>>k>>q;
    vector<vector<ll> >dp(n+1,vector<ll>(min(k+1,n),inf));
    while(q--)
    {
        ll node_x,node_y;
        cin>>node_x>>node_y;
        for(ll i=0;i<=min(k,n-1);i++)
        {
            for(ll node=1;node<=n;node++)dp[node][i]=inf;
        }
        dp[node_x][0]=0;
        queue<node>q;
        q.push({0,node_x,0});
        while(!q.empty())
        {
            ll value=q.front().value;
            ll x=q.front().x;
            ll used=q.front().used;
            q.pop();
            if(used==min(k,m))continue;
            if(dp[x][used]!=value)continue;
            for(ii u:a[x])
            {
                ll node=u.x;
                ll cost=u.y;
                if(minimize(dp[node][used+1],dp[x][used]+cost))
                {
                    q.push({dp[node][used+1],node,used+1});
                }
            }
        }
        ll ans=inf;
        for(ll i=0;i<=min(k,n-1);i++)ans=min(ans,dp[node_y][i]);
        cout<<(ans==inf?-1:ans)<<endl;;

    }
}

Subtask #1
15.0 / 15.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 332 KB Output is correct
2 Correct 13 ms 352 KB Output is correct
3 Correct 26 ms 332 KB Output is correct
4 Correct 22 ms 332 KB Output is correct
5 Correct 57 ms 368 KB Output is correct
6 Correct 81 ms 492 KB Output is correct
7 Correct 138 ms 460 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 522 ms 348 KB Output is correct
8 Execution timed out 1080 ms 380 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 10 ms 332 KB Output is correct
8 Correct 13 ms 352 KB Output is correct
9 Correct 26 ms 332 KB Output is correct
10 Correct 22 ms 332 KB Output is correct
11 Correct 57 ms 368 KB Output is correct
12 Correct 81 ms 492 KB Output is correct
13 Correct 138 ms 460 KB Output is correct
14 Correct 522 ms 348 KB Output is correct
15 Execution timed out 1080 ms 380 KB Time limit exceeded
16 Halted 0 ms 0 KB -