oj.uz

Submission #526929

# Submission time Handle Problem Language Result Execution time Memory
526929 2022-02-16T16:44:17 Z oneloveforever Autobus (COCI22_autobus) C++14
30 / 70
 1000 ms 512 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,m+1),inf));
    while(q--)
    {
        ll node_x,node_y;
        cin>>node_x>>node_y;
        for(ll i=0;i<=min(k,m);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,m);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 1 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 348 KB Output is correct
2 Correct 13 ms 336 KB Output is correct
3 Correct 26 ms 356 KB Output is correct
4 Correct 23 ms 332 KB Output is correct
5 Correct 60 ms 332 KB Output is correct
6 Correct 63 ms 512 KB Output is correct
7 Correct 136 ms 480 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 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 506 ms 352 KB Output is correct
8 Execution timed out 1064 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 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 10 ms 348 KB Output is correct
8 Correct 13 ms 336 KB Output is correct
9 Correct 26 ms 356 KB Output is correct
10 Correct 23 ms 332 KB Output is correct
11 Correct 60 ms 332 KB Output is correct
12 Correct 63 ms 512 KB Output is correct
13 Correct 136 ms 480 KB Output is correct
14 Correct 506 ms 352 KB Output is correct
15 Execution timed out 1064 ms 380 KB Time limit exceeded
16 Halted 0 ms 0 KB -