oj.uz

Submission #526711

# Submission time Handle Problem Language Result Execution time Memory
526711 2022-02-16T02:41:35 Z beepbeepsheep Autobus (COCI22_autobus) C++17
30 / 70
 1000 ms 412 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ii pair<ll,ll>
#define iii pair<ll,ii>
#define endl '\n'
const ll inf=1e15;
const ll mod=1e9+7;
const ll maxn=71;

ll adj[maxn][maxn];
ll dis[maxn][maxn];
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    for (int i=0;i<maxn;i++){
        for (int j=0;j<maxn;j++){
            adj[i][j]=inf;
        }
        adj[i][i]=0;
    }
    ll n,e,a,b,w;
    cin>>n>>e;
    for (int i=0;i<e;i++){
        cin>>a>>b>>w;
        adj[a][b]=min(adj[a][b],w);
    }
    ll k,y,u,x;
    cin>>k>>y;
    queue<ii> q;
    for (int i=0;i<y;i++){
        cin>>a>>b;
        memset(dis,-1,sizeof(dis));
        q.emplace(a,0);
        dis[a][0]=0;
        while (q.size()){
            u=q.front().first;
            x=q.front().second;
            q.pop();
            if (x>k) continue;
            for (int i=1;i<=n;i++){
                if (dis[i][x+1]!=-1){
                    dis[i][x+1]=min(dis[i][x+1],dis[u][x]+adj[u][i]);
                } else{
                    dis[i][x+1]=dis[u][x]+adj[u][i];
                    q.emplace(i,x+1);
                }
            }
        }
        ll ans=inf;
        for (int i=0;i<=k;i++){
            if (dis[b][i]!=-1) ans=min(ans,dis[b][i]);
        }
        cout<<(ans==inf?-1:ans)<<endl;
    }
    return 0;
}

Subtask #1
15.0 / 15.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 400 KB Output is correct
2 Correct 68 ms 404 KB Output is correct
3 Correct 100 ms 332 KB Output is correct
4 Correct 65 ms 400 KB Output is correct
5 Correct 95 ms 400 KB Output is correct
6 Correct 64 ms 332 KB Output is correct
7 Correct 94 ms 392 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 777 ms 412 KB Output is correct
8 Execution timed out 1085 ms 392 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 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 40 ms 400 KB Output is correct
8 Correct 68 ms 404 KB Output is correct
9 Correct 100 ms 332 KB Output is correct
10 Correct 65 ms 400 KB Output is correct
11 Correct 95 ms 400 KB Output is correct
12 Correct 64 ms 332 KB Output is correct
13 Correct 94 ms 392 KB Output is correct
14 Correct 777 ms 412 KB Output is correct
15 Execution timed out 1085 ms 392 KB Time limit exceeded
16 Halted 0 ms 0 KB -