Submission #41166

# Submission time Handle Problem Language Result Execution time Memory
41166 2018-02-13T07:54:19 Z ngkan146 Commuter Pass (JOI18_commuter_pass) C++11
100 / 100
402 ms 97436 KB
#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct edge{
    int v, w;
    edge(int v=0,int w=0): v(v), w(w) {}
};
int n,m,s,t,u,v;
vector <edge> G[100005];
vector <int> dag[100005];
ll dis[100005], disS[100005], disU[100005], disV[100005];
bool visited[100005];
priority_queue <pair<long long,int>, vector<pair<long long,int> >, greater<pair<long long, int> > > pq;
void dijkstra(int root){
    fill(dis+1,dis+n+1, (ll) 1e18);
    fill(visited,visited+n+1,0);
    dis[root] = 0;
    pq.push(pair<ll,int>(0ll, root));
    while(pq.size()){
        int u = pq.top().second;
        pq.pop();
        if (visited[u]) continue;
        visited[u] = 1;
        for(auto v: G[u]){
            if (dis[v.v] > dis[u] + v.w)
                dis[v.v] = dis[u] + v.w,
                pq.push(pair<ll,int>(dis[v.v], v.v));
        }
    }
}
void trailBack(int u){
    if (visited[u]) return;
    visited[u] = 1;
    for(auto v: G[u]){
        if (disS[v.v] == disS[u] - v.w)
            dag[v.v].push_back(u),
            trailBack(v.v);
    }
}
ll ans = (ll) 1e18;
ll value[100005];
void dfs(int u){
    value[u] = (ll) disV[u];
    for(int v: dag[u]){
        if (value[v] == -1) dfs(v);
        value[u] = min(value[u], value[v]);
    }
    ans = min(ans, disU[u] + value[u]);
}
int main(){
    iostream::sync_with_stdio(0);
    cin >> n >> m >> s >> t >> u >> v;
    for(int i=1;i<=m;i++){
        int a,b,c;
        cin >> a >> b >> c;
        G[a].push_back(edge(b, c));
        G[b].push_back(edge(a, c));
    }
    dijkstra(s);
    for(int i=1;i<=n;i++)   disS[i] = dis[i];
    fill(visited+1,visited+n+1,0);
    trailBack(t);
    dijkstra(u);
    for(int i=1;i<=n;i++)   disU[i] = dis[i];
    ans = disU[v];
    dijkstra(v);
    for(int i=1;i<=n;i++)   disV[i] = dis[i];
    fill(value+1,value+1+n,-1);
    dfs(s);
    swap(disU, disV);
    fill(value+1,value+1+n,-1);
    dfs(s);
    cout << ans;
}
# Verdict Execution time Memory Grader output
1 Correct 294 ms 16612 KB Output is correct
2 Correct 342 ms 16956 KB Output is correct
3 Correct 348 ms 24720 KB Output is correct
4 Correct 301 ms 24720 KB Output is correct
5 Correct 331 ms 28696 KB Output is correct
6 Correct 311 ms 31780 KB Output is correct
7 Correct 347 ms 36504 KB Output is correct
8 Correct 337 ms 39768 KB Output is correct
9 Correct 305 ms 42504 KB Output is correct
10 Correct 250 ms 46936 KB Output is correct
11 Correct 110 ms 48328 KB Output is correct
12 Correct 320 ms 53412 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 335 ms 55164 KB Output is correct
2 Correct 332 ms 55440 KB Output is correct
3 Correct 346 ms 55440 KB Output is correct
4 Correct 344 ms 55440 KB Output is correct
5 Correct 350 ms 55824 KB Output is correct
6 Correct 355 ms 57380 KB Output is correct
7 Correct 378 ms 58132 KB Output is correct
8 Correct 371 ms 58132 KB Output is correct
9 Correct 360 ms 58132 KB Output is correct
10 Correct 360 ms 58132 KB Output is correct
11 Correct 150 ms 58132 KB Output is correct
12 Correct 381 ms 58132 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 16 ms 58132 KB Output is correct
2 Correct 7 ms 58132 KB Output is correct
3 Correct 7 ms 58132 KB Output is correct
4 Correct 23 ms 58132 KB Output is correct
5 Correct 15 ms 58132 KB Output is correct
6 Correct 8 ms 58132 KB Output is correct
7 Correct 9 ms 58132 KB Output is correct
8 Correct 9 ms 58132 KB Output is correct
9 Correct 8 ms 58132 KB Output is correct
10 Correct 16 ms 58132 KB Output is correct
11 Correct 8 ms 58132 KB Output is correct
12 Correct 7 ms 58132 KB Output is correct
13 Correct 7 ms 58132 KB Output is correct
14 Correct 9 ms 58132 KB Output is correct
15 Correct 8 ms 58132 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 294 ms 16612 KB Output is correct
2 Correct 342 ms 16956 KB Output is correct
3 Correct 348 ms 24720 KB Output is correct
4 Correct 301 ms 24720 KB Output is correct
5 Correct 331 ms 28696 KB Output is correct
6 Correct 311 ms 31780 KB Output is correct
7 Correct 347 ms 36504 KB Output is correct
8 Correct 337 ms 39768 KB Output is correct
9 Correct 305 ms 42504 KB Output is correct
10 Correct 250 ms 46936 KB Output is correct
11 Correct 110 ms 48328 KB Output is correct
12 Correct 320 ms 53412 KB Output is correct
13 Correct 335 ms 55164 KB Output is correct
14 Correct 332 ms 55440 KB Output is correct
15 Correct 346 ms 55440 KB Output is correct
16 Correct 344 ms 55440 KB Output is correct
17 Correct 350 ms 55824 KB Output is correct
18 Correct 355 ms 57380 KB Output is correct
19 Correct 378 ms 58132 KB Output is correct
20 Correct 371 ms 58132 KB Output is correct
21 Correct 360 ms 58132 KB Output is correct
22 Correct 360 ms 58132 KB Output is correct
23 Correct 150 ms 58132 KB Output is correct
24 Correct 381 ms 58132 KB Output is correct
25 Correct 16 ms 58132 KB Output is correct
26 Correct 7 ms 58132 KB Output is correct
27 Correct 7 ms 58132 KB Output is correct
28 Correct 23 ms 58132 KB Output is correct
29 Correct 15 ms 58132 KB Output is correct
30 Correct 8 ms 58132 KB Output is correct
31 Correct 9 ms 58132 KB Output is correct
32 Correct 9 ms 58132 KB Output is correct
33 Correct 8 ms 58132 KB Output is correct
34 Correct 16 ms 58132 KB Output is correct
35 Correct 8 ms 58132 KB Output is correct
36 Correct 7 ms 58132 KB Output is correct
37 Correct 7 ms 58132 KB Output is correct
38 Correct 9 ms 58132 KB Output is correct
39 Correct 8 ms 58132 KB Output is correct
40 Correct 292 ms 59624 KB Output is correct
41 Correct 307 ms 63872 KB Output is correct
42 Correct 353 ms 68064 KB Output is correct
43 Correct 141 ms 71464 KB Output is correct
44 Correct 173 ms 73700 KB Output is correct
45 Correct 402 ms 78064 KB Output is correct
46 Correct 377 ms 81316 KB Output is correct
47 Correct 328 ms 82944 KB Output is correct
48 Correct 170 ms 84568 KB Output is correct
49 Correct 255 ms 88448 KB Output is correct
50 Correct 375 ms 93192 KB Output is correct
51 Correct 385 ms 97436 KB Output is correct