oj.uz

Submission #696622

# Submission time Handle Problem Language Result Execution time Memory
696622 2023-02-07T01:42:53 Z mousey Autobus (COCI22_autobus) C++14
15 / 70
 1000 ms 189712 KB 
#include <bits/stdc++.h>
#define int long long
#define vi vector <int>
#define vv vector <vi>
#define pi pair <int, int>
#define vip vector <pi>
#define pb push_back
#define f first
#define s second
#define nl cout<<"\n"
using namespace std;

const int mod=1e9+7;
const double eps=1e-9;
const int N=70;
int n, m, k, q, w[N+5][N+5];
int dist[N+5][N+5][N*N+5];
bool used[N+5][N*N+5];

void input()
{
	cin >> n >> m;
	for(int i = 1; i <= m; i++)
	{
		int u, v, t;
		cin >> u >> v >> t;
		if(!w[u][v]) w[u][v]=t;
		else w[u][v]=min(w[u][v], t);
	}
	cin >> k >> q;
}

void solve()
{
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            for(int p = 0; p <= n*n; p++)
            {
                dist[i][j][p]=LLONG_MAX;
            }
        }
    }
	for(int i = 1; i <= n; i++)
	{
		priority_queue <pair <int, pi> > pq;
		pq.push({LLONG_MAX-0, {i, 0}});
		dist[i][i][0]=0;
		while(!pq.empty())
		{
			pi p=pq.top().s;
			pq.pop();
			if(used[p.f][p.s]) continue;
			if(p.s==n*n) continue;
			for(int j = 1; j <= n; j++)
			{
				if(!w[p.f][j]) continue;
				if(dist[i][j][p.s+1]>dist[i][p.f][p.s]+w[p.f][j])
				{
					dist[i][j][p.s+1]=dist[i][p.f][p.s]+w[p.f][j];
					pq.push({LLONG_MAX-dist[i][j][p.s+1], {j, p.s+1}});
				}
			}
			used[p.f][p.s]=true;
		}
		for(int j = 1; j <= n; j++)
		{
			used[j][0]=false;
			for(int p = 1; p <= n*n; p++)
			{
				used[j][p]=false;
				dist[i][j][p]=min(dist[i][j][p-1], dist[i][j][p]);
			}
		}
	}
	if(k>n*n) k=n*n;
	while(q--)
	{
		int u, v;
		cin >> u >> v;
		if(dist[u][v][k]==LLONG_MAX) cout << -1;
		else cout << dist[u][v][k];
		nl;
	}
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t=1;
//    freopen("math.inp", "r", stdin);
//    freopen("math.out", "w", stdout);
//    cin >> t;
    for(int i = 1; i <= t; i++)
    {
        input();
        solve();
        nl;
    }
}

/*
6
a
b
c
d
e
f
*/

Subtask #1
15.0 / 15.0

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

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1103 ms 189212 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Execution timed out 1093 ms 189712 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Execution timed out 1103 ms 189212 KB Time limit exceeded
8 Halted 0 ms 0 KB -