oj.uz

Submission #880542

# Submission time Handle Problem Language Result Execution time Memory
880542 2023-11-29T16:01:38 Z tsumondai Autobus (COCI22_autobus) C++14
15 / 70
 1000 ms 27544 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, r, l) for(int i = r; i >= l; i--)
#define __TIME  (1.0 * clock() / CLOCKS_PER_SEC)

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
 
const int N = 1e6 + 5;
 
const int oo = 1e9, mod = 1e9 + 7;
 
int n, m, k, q, c[75][75], visited[71];
string s;
vector<ii> adj[N];

// precalc

struct Node {
	int vec, cnt_=0, sum_=0;
};

void bfs(int s, int t) {
	if (s==t) {
		cout << 0 << '\n';
		return;
	}
	int ans=oo, pepe=0;
	queue<Node> q;
	visited[s]=true;
	q.push({s, 0, 0});
	while (!q.empty()) {
		pepe++;
		if (pepe >= 80*80) break;
		Node tmp=q.front(); q.pop();
		int u=tmp.vec, cnt=tmp.cnt_, sum=tmp.sum_;
		//cout << u << ' ';
		if (u==t) {
			if (cnt<=k) ans=min(ans, sum);
			//cout << cnt << ' ' << sum << '\n';
		}
		for (ii tmp_: adj[u]) {
			int v=tmp_.se, dis=tmp_.fi;
			Node newNode;
			newNode.vec=v;
			newNode.cnt_=cnt+1;
			newNode.sum_=sum+dis;
			if (cnt+1>k) continue;
			q.push(newNode);
		}
	}
	if (ans==oo) ans=-1;
	cout << ans << '\n';
	return;
}

void process() {
	memset(c, 0x3f, sizeof(c));
	cin >> n >> m;
	foru(i,1,m) {
		int u, v, t; cin >> u >> v >> t;
		c[u][v]=min(c[u][v], t);
	}
	// shortest path at most k path

	foru(i,1,n) {
		foru(j,1,n) {
			if (c[i][j]<=1e6+1) {
				adj[i].pb({c[i][j], j});
			}
		}
	}


	cin >> k >> q;

	k=min(k,n);

	while (q--) {
		int s, t;
		cin >> s >> t;
		bfs(s,t);
	}

    return;
}

signed main() {
    cin.tie(0)->sync_with_stdio(false);
    //freopen(".inp", "r", stdin);
    //freopen(".out", "w", stdout);
    process();
    cerr << "Time elapsed: " << __TIME << " s.\n";
    return 0;
}

/*
Xét các trường hợp đặc biệt
Kiểm tra lại input/output
Cố gắng trâu
Lật ngược bài toán
Keep calm and get VOI 
Flow:

*/

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 23900 KB Output is correct
2 Correct 5 ms 23900 KB Output is correct
3 Correct 5 ms 23900 KB Output is correct
4 Correct 6 ms 23932 KB Output is correct
5 Correct 6 ms 23900 KB Output is correct
6 Correct 7 ms 23900 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 23900 KB Output is correct
2 Correct 9 ms 23900 KB Output is correct
3 Correct 31 ms 24032 KB Output is correct
4 Correct 33 ms 23900 KB Output is correct
5 Correct 418 ms 24144 KB Output is correct
6 Correct 455 ms 23900 KB Output is correct
7 Execution timed out 1042 ms 27544 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

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

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 23900 KB Output is correct
2 Correct 5 ms 23900 KB Output is correct
3 Correct 5 ms 23900 KB Output is correct
4 Correct 6 ms 23932 KB Output is correct
5 Correct 6 ms 23900 KB Output is correct
6 Correct 7 ms 23900 KB Output is correct
7 Correct 6 ms 23900 KB Output is correct
8 Correct 9 ms 23900 KB Output is correct
9 Correct 31 ms 24032 KB Output is correct
10 Correct 33 ms 23900 KB Output is correct
11 Correct 418 ms 24144 KB Output is correct
12 Correct 455 ms 23900 KB Output is correct
13 Execution timed out 1042 ms 27544 KB Time limit exceeded
14 Halted 0 ms 0 KB -