# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
405866 |
2021-05-17T01:06:36 Z |
thomas_li |
Toll (BOI17_toll) |
C++17 |
|
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";
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3071 ms |
7420 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3031 ms |
4480 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
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 |
# |
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 |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3071 ms |
7420 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |