oj.uz

Submission #880541

# Submission time Handle Problem Language Result Execution time Memory
880541 2023-11-29T15:59:28 Z tsumondai Autobus (COCI22_autobus) C++14
15 / 70
 1000 ms 27092 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;

	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 5 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 5 ms 23900 KB Output is correct
5 Correct 5 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 10 ms 23900 KB Output is correct
3 Correct 31 ms 23900 KB Output is correct
4 Correct 34 ms 23900 KB Output is correct
5 Correct 414 ms 24132 KB Output is correct
6 Correct 467 ms 24188 KB Output is correct
7 Execution timed out 1055 ms 27092 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 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 5 ms 23900 KB Output is correct
5 Correct 5 ms 23900 KB Output is correct
6 Correct 7 ms 23900 KB Output is correct
7 Execution timed out 1033 ms 25020 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 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 5 ms 23900 KB Output is correct
5 Correct 5 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 10 ms 23900 KB Output is correct
9 Correct 31 ms 23900 KB Output is correct
10 Correct 34 ms 23900 KB Output is correct
11 Correct 414 ms 24132 KB Output is correct
12 Correct 467 ms 24188 KB Output is correct
13 Execution timed out 1055 ms 27092 KB Time limit exceeded
14 Halted 0 ms 0 KB -