oj.uz

Submission #41164

# Submission time Handle Problem Language Result Execution time Memory
41164 2018-02-13T07:51:32 Z ngkan146 Commuter Pass (JOI18_commuter_pass) C++11
15 / 100
 2000 ms 20448 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 dfs(int u){
    ll mini = (ll) disV[u];
    for(int v: dag[u]){
        mini = min(mini, dfs(v));
    }
    ans = min(ans, disU[u] + mini);
    return mini;
}
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];
    dfs(s);
    swap(disU, disV);
    dfs(s);
    cout << ans;
}

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 293 ms 15716 KB Output is correct
2 Execution timed out 2055 ms 16348 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 347 ms 17448 KB Output is correct
2 Correct 354 ms 17600 KB Output is correct
3 Correct 368 ms 17600 KB Output is correct
4 Correct 368 ms 17600 KB Output is correct
5 Correct 380 ms 18212 KB Output is correct
6 Correct 375 ms 19752 KB Output is correct
7 Correct 407 ms 20448 KB Output is correct
8 Correct 366 ms 20448 KB Output is correct
9 Correct 384 ms 20448 KB Output is correct
10 Correct 361 ms 20448 KB Output is correct
11 Correct 145 ms 20448 KB Output is correct
12 Correct 358 ms 20448 KB Output is correct

Subtask #3
0 / 24.0

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

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 293 ms 15716 KB Output is correct
2 Execution timed out 2055 ms 16348 KB Time limit exceeded
3 Halted 0 ms 0 KB -