oj.uz

Submission #526936

# Submission time Handle Problem Language Result Execution time Memory
526936 2022-02-16T16:50:57 Z oneloveforever Autobus (COCI22_autobus) C++14
30 / 70
 1000 ms 508 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,n-1))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 0 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 14 ms 332 KB Output is correct
2 Correct 19 ms 356 KB Output is correct
3 Correct 28 ms 356 KB Output is correct
4 Correct 28 ms 372 KB Output is correct
5 Correct 66 ms 360 KB Output is correct
6 Correct 63 ms 508 KB Output is correct
7 Correct 170 ms 488 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 505 ms 360 KB Output is correct
8 Execution timed out 1088 ms 488 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 14 ms 332 KB Output is correct
8 Correct 19 ms 356 KB Output is correct
9 Correct 28 ms 356 KB Output is correct
10 Correct 28 ms 372 KB Output is correct
11 Correct 66 ms 360 KB Output is correct
12 Correct 63 ms 508 KB Output is correct
13 Correct 170 ms 488 KB Output is correct
14 Correct 505 ms 360 KB Output is correct
15 Execution timed out 1088 ms 488 KB Time limit exceeded
16 Halted 0 ms 0 KB -