oj.uz

Submission #405866

# Submission time Handle Problem Language Result Execution time Memory
405866 2021-05-17T01:06:36 Z thomas_li Toll (BOI17_toll) C++17
8 / 100
 3000 ms 8260 KB 
// 57?
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
const int MM = 5e4+5;
int n,o,k,m; ll dp[MM]; vector<pi> adj[MM];

int dfs(int u, int b){
	if(dp[u] != -1) return dp[u];
	if(u == b){
		dp[u] = 0;
		return 0;
	}
	dp[u] = 1e9;
	for(auto [v,w] : adj[u]){
		dfs(v,b);
		dp[u] =min(dp[u],dp[v]+w);
	}
	return dp[u];
}

int main(){
	cin.tie(0)->sync_with_stdio(0);
	cin >> k >> n >> m >> o;
	for(int i = 0; i < m; i++){
		int a,b,t; cin >> a >> b >> t;
		adj[a].emplace_back(b,t);
	}
	while(o--){
		int a,b; cin >> a >> b;
		memset(dp,-1,sizeof dp);
		dfs(a,b);
		cout << (dp[a]>=1e9 ? -1 : dp[a]) << "\n";
	}
}

Subtask #1
0 / 7.0

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

Subtask #2
0 / 10.0

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

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1868 KB Output is correct
2 Correct 2 ms 1868 KB Output is correct
3 Correct 2 ms 1868 KB Output is correct
4 Correct 2 ms 1868 KB Output is correct
5 Correct 2 ms 1868 KB Output is correct
6 Correct 3 ms 1868 KB Output is correct
7 Correct 5 ms 1912 KB Output is correct
8 Correct 7 ms 1996 KB Output is correct
9 Correct 7 ms 1996 KB Output is correct
10 Correct 25 ms 4564 KB Output is correct
11 Correct 165 ms 6980 KB Output is correct
12 Correct 224 ms 7812 KB Output is correct
13 Correct 209 ms 8260 KB Output is correct
14 Correct 177 ms 6944 KB Output is correct
15 Correct 118 ms 4800 KB Output is correct
16 Correct 117 ms 4804 KB Output is correct

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1868 KB Output is correct
2 Correct 2 ms 1868 KB Output is correct
3 Correct 2 ms 1868 KB Output is correct
4 Correct 2 ms 1868 KB Output is correct
5 Correct 2 ms 1868 KB Output is correct
6 Correct 3 ms 1868 KB Output is correct
7 Correct 5 ms 1912 KB Output is correct
8 Correct 7 ms 1996 KB Output is correct
9 Correct 7 ms 1996 KB Output is correct
10 Correct 25 ms 4564 KB Output is correct
11 Correct 165 ms 6980 KB Output is correct
12 Correct 224 ms 7812 KB Output is correct
13 Correct 209 ms 8260 KB Output is correct
14 Correct 177 ms 6944 KB Output is correct
15 Correct 118 ms 4800 KB Output is correct
16 Correct 117 ms 4804 KB Output is correct
17 Execution timed out 3069 ms 7188 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

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