| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 316289 | 2020-10-25T19:15:40 Z | tushar_2658 | Commuter Pass (JOI18_commuter_pass) | C++14 | 494 ms | 31956 KB |
#include "bits/stdc++.h"
using namespace std;
const int maxn = 100005;
using ll = long long;
vector<pair<int, ll>> edges[maxn];
ll dis[3][maxn];
vector<int> g[maxn], rg[maxn];
int n, m;
void dijkstra(int id, int s){
memset(dis[id], 63, sizeof dis[id]);
dis[id][s] = 0;
using pii = pair<ll, int>;
priority_queue<pii, vector<pii>, greater<pii>> pq;
pq.push({0, s});
vector<int> vis(n + 1);
while(!pq.empty()){
pii src = pq.top();
pq.pop();
if(vis[src.second])continue;
vis[src.second] = 1;
for(auto i : edges[src.second]){
ll cost = dis[id][src.second] + i.second;
if(dis[id][i.first] > cost){
dis[id][i.first] = cost;
pq.push({cost, i.first});
}
}
}
}
ll dp[2][maxn];
int vis[maxn], deg[maxn];
vector<int> order;
void dfs(int x){
vis[x] = 1;
for(auto i : g[x]){
if(!vis[i]){
dfs(i);
}
}
order.push_back(x);
}
int main(int argc, char const *argv[])
{
scanf("%d %d", &n, &m);
int s, t, u, v;
scanf("%d %d", &s, &t);
scanf("%d %d", &u, &v);
for(int i = 0; i < m; ++i){
int x, y;
ll c;
scanf("%d %d %lld", &x, &y, &c);
edges[x].push_back({y, c});
edges[y].push_back({x, c});
}
dijkstra(0, s);
dijkstra(1, u);
dijkstra(2, v);
queue<int> q;
q.push(t);
vector<int> vis(n + 1);
while(!q.empty()){
int src = q.front();
q.pop();
if(vis[src])continue;
vis[src] = 1;
for(auto i : edges[src]){
ll cost = dis[0][i.first] + i.second;
if(dis[0][src] == cost){
g[i.first].push_back(src);
deg[src]++;
q.push(i.first);
}
}
}
dfs(s);
ll ans = dis[1][v];
for(auto i : order){
dp[0][i] = dis[1][i];
dp[1][i] = dis[2][i];
for(auto j : g[i]){
dp[0][i] = min(dp[0][i], dp[0][j]);
dp[1][i] = min(dp[1][i], dp[1][j]);
}
ans = min(ans, dis[1][i] + dp[1][i]);
ans = min(ans, dis[2][i] + dp[0][i]);
}
cout << ans << endl;
return 0;
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 344 ms | 27528 KB | Output is correct |
| 2 | Correct | 376 ms | 26848 KB | Output is correct |
| 3 | Correct | 396 ms | 31956 KB | Output is correct |
| 4 | Correct | 338 ms | 27368 KB | Output is correct |
| 5 | Correct | 377 ms | 27864 KB | Output is correct |
| 6 | Correct | 356 ms | 27600 KB | Output is correct |
| 7 | Correct | 381 ms | 28096 KB | Output is correct |
| 8 | Correct | 370 ms | 27996 KB | Output is correct |
| 9 | Correct | 344 ms | 26624 KB | Output is correct |
| 10 | Correct | 299 ms | 26700 KB | Output is correct |
| 11 | Correct | 169 ms | 23136 KB | Output is correct |
| 12 | Correct | 369 ms | 26508 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 407 ms | 28208 KB | Output is correct |
| 2 | Correct | 392 ms | 28348 KB | Output is correct |
| 3 | Correct | 386 ms | 27844 KB | Output is correct |
| 4 | Correct | 394 ms | 28216 KB | Output is correct |
| 5 | Correct | 398 ms | 29176 KB | Output is correct |
| 6 | Correct | 381 ms | 31028 KB | Output is correct |
| 7 | Correct | 432 ms | 31624 KB | Output is correct |
| 8 | Correct | 393 ms | 28316 KB | Output is correct |
| 9 | Correct | 384 ms | 29012 KB | Output is correct |
| 10 | Correct | 423 ms | 27964 KB | Output is correct |
| 11 | Correct | 189 ms | 24804 KB | Output is correct |
| 12 | Correct | 427 ms | 31380 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 19 ms | 11512 KB | Output is correct |
| 2 | Correct | 7 ms | 9728 KB | Output is correct |
| 3 | Correct | 7 ms | 9728 KB | Output is correct |
| 4 | Correct | 28 ms | 13056 KB | Output is correct |
| 5 | Correct | 17 ms | 11392 KB | Output is correct |
| 6 | Correct | 8 ms | 9856 KB | Output is correct |
| 7 | Correct | 8 ms | 9856 KB | Output is correct |
| 8 | Correct | 11 ms | 9984 KB | Output is correct |
| 9 | Correct | 8 ms | 9856 KB | Output is correct |
| 10 | Correct | 19 ms | 11392 KB | Output is correct |
| 11 | Correct | 7 ms | 9728 KB | Output is correct |
| 12 | Correct | 8 ms | 9728 KB | Output is correct |
| 13 | Correct | 8 ms | 9728 KB | Output is correct |
| 14 | Correct | 7 ms | 9856 KB | Output is correct |
| 15 | Correct | 8 ms | 9888 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 344 ms | 27528 KB | Output is correct |
| 2 | Correct | 376 ms | 26848 KB | Output is correct |
| 3 | Correct | 396 ms | 31956 KB | Output is correct |
| 4 | Correct | 338 ms | 27368 KB | Output is correct |
| 5 | Correct | 377 ms | 27864 KB | Output is correct |
| 6 | Correct | 356 ms | 27600 KB | Output is correct |
| 7 | Correct | 381 ms | 28096 KB | Output is correct |
| 8 | Correct | 370 ms | 27996 KB | Output is correct |
| 9 | Correct | 344 ms | 26624 KB | Output is correct |
| 10 | Correct | 299 ms | 26700 KB | Output is correct |
| 11 | Correct | 169 ms | 23136 KB | Output is correct |
| 12 | Correct | 369 ms | 26508 KB | Output is correct |
| 13 | Correct | 407 ms | 28208 KB | Output is correct |
| 14 | Correct | 392 ms | 28348 KB | Output is correct |
| 15 | Correct | 386 ms | 27844 KB | Output is correct |
| 16 | Correct | 394 ms | 28216 KB | Output is correct |
| 17 | Correct | 398 ms | 29176 KB | Output is correct |
| 18 | Correct | 381 ms | 31028 KB | Output is correct |
| 19 | Correct | 432 ms | 31624 KB | Output is correct |
| 20 | Correct | 393 ms | 28316 KB | Output is correct |
| 21 | Correct | 384 ms | 29012 KB | Output is correct |
| 22 | Correct | 423 ms | 27964 KB | Output is correct |
| 23 | Correct | 189 ms | 24804 KB | Output is correct |
| 24 | Correct | 427 ms | 31380 KB | Output is correct |
| 25 | Correct | 19 ms | 11512 KB | Output is correct |
| 26 | Correct | 7 ms | 9728 KB | Output is correct |
| 27 | Correct | 7 ms | 9728 KB | Output is correct |
| 28 | Correct | 28 ms | 13056 KB | Output is correct |
| 29 | Correct | 17 ms | 11392 KB | Output is correct |
| 30 | Correct | 8 ms | 9856 KB | Output is correct |
| 31 | Correct | 8 ms | 9856 KB | Output is correct |
| 32 | Correct | 11 ms | 9984 KB | Output is correct |
| 33 | Correct | 8 ms | 9856 KB | Output is correct |
| 34 | Correct | 19 ms | 11392 KB | Output is correct |
| 35 | Correct | 7 ms | 9728 KB | Output is correct |
| 36 | Correct | 8 ms | 9728 KB | Output is correct |
| 37 | Correct | 8 ms | 9728 KB | Output is correct |
| 38 | Correct | 7 ms | 9856 KB | Output is correct |
| 39 | Correct | 8 ms | 9888 KB | Output is correct |
| 40 | Correct | 353 ms | 27420 KB | Output is correct |
| 41 | Correct | 380 ms | 26584 KB | Output is correct |
| 42 | Correct | 356 ms | 26704 KB | Output is correct |
| 43 | Correct | 216 ms | 26044 KB | Output is correct |
| 44 | Correct | 224 ms | 25844 KB | Output is correct |
| 45 | Correct | 494 ms | 29620 KB | Output is correct |
| 46 | Correct | 443 ms | 29488 KB | Output is correct |
| 47 | Correct | 362 ms | 27328 KB | Output is correct |
| 48 | Correct | 250 ms | 23776 KB | Output is correct |
| 49 | Correct | 322 ms | 27000 KB | Output is correct |
| 50 | Correct | 430 ms | 28968 KB | Output is correct |
| 51 | Correct | 413 ms | 29604 KB | Output is correct |