oj.uz

Submission #42113

# Submission time Handle Problem Language Result Execution time Memory
42113 2018-02-22T16:36:53 Z nonocut Commuter Pass (JOI18_commuter_pass) C++14
15 / 100
 2000 ms 262144 KB 
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back
#define X first
#define Y second
const int maxn = 100005;
const ll inf = 1e18;

struct node {
    int x;
    ll val;
    node(int _x = 0, ll _val = 0) {
        x = _x; val = _val;
    };
    bool operator < (node a) const {
        return a.val<val;
    }
};

int n,m,a,b,c,d;

bool vis[maxn];
ll dist[maxn], da[maxn], db[maxn], dc[maxn], dd[maxn];
vector<pair<int,ll>> way[maxn];
priority_queue<node> heap;

vector<int> from[maxn];
vector<int> topo;
ll mn[maxn];
ll ans;

void sssp(int u) {
    for(int i=1;i<=n;i++) dist[i] = inf, vis[i] = 0;
    dist[u] = 0;
    heap.push(node(u,0));
    while(!heap.empty()) {
        int u = heap.top().x; heap.pop();
        if(vis[u]) continue;
        vis[u] = 1;
        for(auto t : way[u]) {
            if(dist[t.X] > dist[u] + t.Y) {
                dist[t.X] = dist[u] + t.Y;
                heap.push(node(t.X,dist[t.X]));
            }
        }
    }
}

void tsort(int u) {
    for(auto v : from[u]) tsort(v);
    topo.push_back(u);
}

void solve() {
    for(int x=1;x<=n;x++) mn[x] = dc[x];
    for(auto u : topo) {
        ans = min(ans, mn[u] + dd[u]);
        for(auto v : from[u]) {
            mn[v] = min(mn[v], mn[u]);
        }
    }
}

int main() {
    scanf("%d%d",&n,&m);
    scanf("%d%d%d%d",&a,&b,&c,&d);
    for(int i=0;i<m;i++) {
        int x,y; ll val;
        scanf("%d%d%lld",&x,&y,&val);
        way[x].pb({y,val}); way[y].pb({x,val});
    }
    sssp(a); for(int i=1;i<=n;i++) da[i] = dist[i];
    sssp(b); for(int i=1;i<=n;i++) db[i] = dist[i];
    sssp(c); for(int i=1;i<=n;i++) dc[i] = dist[i];
    sssp(d); for(int i=1;i<=n;i++) dd[i] = dist[i];
    for(int x=1;x<=n;x++) {
        for(auto t : way[x]) {
            if(da[x]+db[t.X]+t.Y==da[b]) from[x].pb(t.X);
        }
    }
    tsort(a);
    reverse(topo.begin(),topo.end());
    ans = dc[d];
    solve();
    swap(dc,dd);
    solve();
    printf("%lld",ans);
}

Compilation message

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:67:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&m);
                        ^
commuter_pass.cpp:68:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d%d",&a,&b,&c,&d);
                                  ^
commuter_pass.cpp:71:37: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%lld",&x,&y,&val);
                                     ^

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 457 ms 21404 KB Output is correct
2 Execution timed out 2072 ms 262144 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 501 ms 262144 KB Output is correct
2 Correct 482 ms 262144 KB Output is correct
3 Correct 503 ms 262144 KB Output is correct
4 Correct 509 ms 262144 KB Output is correct
5 Correct 524 ms 262144 KB Output is correct
6 Correct 549 ms 262144 KB Output is correct
7 Correct 585 ms 262144 KB Output is correct
8 Correct 530 ms 262144 KB Output is correct
9 Correct 552 ms 262144 KB Output is correct
10 Correct 562 ms 262144 KB Output is correct
11 Correct 266 ms 262144 KB Output is correct
12 Correct 520 ms 262144 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 1110 ms 262144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 457 ms 21404 KB Output is correct
2 Execution timed out 2072 ms 262144 KB Time limit exceeded
3 Halted 0 ms 0 KB -