oj.uz

Submission #216335

# Submission time Handle Problem Language Result Execution time Memory
216335 2020-03-27T06:57:07 Z ToMmyDong Commuter Pass (JOI18_commuter_pass) C++11
100 / 100
 373 ms 24352 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define ALL(i) i.begin(),i.end()
#define SZ(i) int(i.size())
#define eb emplace_back
#define X first
#define Y second
#define MEM(i,a) memset(i,(a),sizeof(i))
#ifdef tmd
#define debug(...) fprintf(stderr,"%d(%s)=",__LINE__,#__VA_ARGS__);_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){
    cerr<<x<<",";
    _do(y...);
}
#define IOS()
#else
#define debug(...)
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define pary(...)
#define endl '\n'
#endif // tmd

const ll INF = 0x3f3f3f3f3f3f3f3f;
const int MAXN = 100005;

vector<pll> edge[MAXN];
int n, m;
pii p1, p2;

struct Dijkstra {
    int src;
    ll dis[MAXN];
    bool vis[MAXN];
    Dijkstra (int nd) : src(nd) {
        memset(dis, 0x3f, sizeof(dis));
        memset(vis, 0, sizeof(vis));
        build();
    }

    void build () {
        priority_queue<pll,vector<pll>,greater<pll>> pq;
        pq.emplace(0, src);
        dis[src] = 0;

        while (pq.size()) {
            int cur = pq.top().Y;
            pq.pop();

            if (vis[cur]) {
                continue;
            }
            vis[cur] = true;

            for (auto p : edge[cur]) {
                if (dis[cur] + p.Y < dis[p.X]) {
                    dis[p.X] = dis[cur] + p.Y;
                    pq.emplace(dis[p.X], p.X);
                }
            }
        }
    }
};

ll mu[MAXN], mv[MAXN];
int main () {
    IOS();

    cin >> n >> m;
    cin >> p1.X >> p1.Y;
    cin >> p2.X >> p2.Y;


    for (int i=0; i<m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        edge[u].eb(v, w);
        edge[v].eb(u, w);
    }

    Dijkstra ds(p1.X), dt(p1.Y), du(p2.X), dv(p2.Y);
    debug(ds.dis[p1.Y]);

    vector<pll> nid;
    nid.reserve(n);

    REP1 (i, n) {
        nid.emplace_back(ds.dis[i], i);
    }
    sort(ALL(nid));

    ll ans = du.dis[p2.Y];
    for (auto p : nid) {
        int nd = p.Y;

        mu[nd] = du.dis[nd];
        mv[nd] = dv.dis[nd];

        for (auto e : edge[nd]) {
            if (ds.dis[e.X] + e.Y == ds.dis[nd]) {
                mu[nd] = min(mu[nd], mu[e.X]);
                mv[nd] = min(mv[nd], mv[e.X]);
            }
        }

        if (ds.dis[p1.Y] == ds.dis[nd] + dt.dis[nd]) {
            ans = min(ans, dv.dis[nd] + mu[nd]);
            ans = min(ans, du.dis[nd] + mv[nd]);
        }

    }


    cout << ans << endl;

    return 0;
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 353 ms 23744 KB Output is correct
2 Correct 348 ms 23436 KB Output is correct
3 Correct 357 ms 23544 KB Output is correct
4 Correct 339 ms 23508 KB Output is correct
5 Correct 348 ms 23484 KB Output is correct
6 Correct 360 ms 23720 KB Output is correct
7 Correct 355 ms 23336 KB Output is correct
8 Correct 333 ms 23320 KB Output is correct
9 Correct 339 ms 24300 KB Output is correct
10 Correct 294 ms 24280 KB Output is correct
11 Correct 134 ms 16632 KB Output is correct
12 Correct 366 ms 24076 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 361 ms 23600 KB Output is correct
2 Correct 356 ms 23408 KB Output is correct
3 Correct 358 ms 23416 KB Output is correct
4 Correct 360 ms 23400 KB Output is correct
5 Correct 360 ms 23428 KB Output is correct
6 Correct 340 ms 23596 KB Output is correct
7 Correct 368 ms 23408 KB Output is correct
8 Correct 357 ms 23400 KB Output is correct
9 Correct 373 ms 23436 KB Output is correct
10 Correct 358 ms 23408 KB Output is correct
11 Correct 142 ms 16632 KB Output is correct
12 Correct 344 ms 23604 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 7552 KB Output is correct
2 Correct 7 ms 6272 KB Output is correct
3 Correct 7 ms 6272 KB Output is correct
4 Correct 24 ms 8832 KB Output is correct
5 Correct 15 ms 7552 KB Output is correct
6 Correct 8 ms 6400 KB Output is correct
7 Correct 9 ms 6400 KB Output is correct
8 Correct 9 ms 6400 KB Output is correct
9 Correct 9 ms 6272 KB Output is correct
10 Correct 16 ms 7552 KB Output is correct
11 Correct 7 ms 6272 KB Output is correct
12 Correct 8 ms 6272 KB Output is correct
13 Correct 8 ms 6272 KB Output is correct
14 Correct 8 ms 6272 KB Output is correct
15 Correct 8 ms 6272 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 353 ms 23744 KB Output is correct
2 Correct 348 ms 23436 KB Output is correct
3 Correct 357 ms 23544 KB Output is correct
4 Correct 339 ms 23508 KB Output is correct
5 Correct 348 ms 23484 KB Output is correct
6 Correct 360 ms 23720 KB Output is correct
7 Correct 355 ms 23336 KB Output is correct
8 Correct 333 ms 23320 KB Output is correct
9 Correct 339 ms 24300 KB Output is correct
10 Correct 294 ms 24280 KB Output is correct
11 Correct 134 ms 16632 KB Output is correct
12 Correct 366 ms 24076 KB Output is correct
13 Correct 361 ms 23600 KB Output is correct
14 Correct 356 ms 23408 KB Output is correct
15 Correct 358 ms 23416 KB Output is correct
16 Correct 360 ms 23400 KB Output is correct
17 Correct 360 ms 23428 KB Output is correct
18 Correct 340 ms 23596 KB Output is correct
19 Correct 368 ms 23408 KB Output is correct
20 Correct 357 ms 23400 KB Output is correct
21 Correct 373 ms 23436 KB Output is correct
22 Correct 358 ms 23408 KB Output is correct
23 Correct 142 ms 16632 KB Output is correct
24 Correct 344 ms 23604 KB Output is correct
25 Correct 16 ms 7552 KB Output is correct
26 Correct 7 ms 6272 KB Output is correct
27 Correct 7 ms 6272 KB Output is correct
28 Correct 24 ms 8832 KB Output is correct
29 Correct 15 ms 7552 KB Output is correct
30 Correct 8 ms 6400 KB Output is correct
31 Correct 9 ms 6400 KB Output is correct
32 Correct 9 ms 6400 KB Output is correct
33 Correct 9 ms 6272 KB Output is correct
34 Correct 16 ms 7552 KB Output is correct
35 Correct 7 ms 6272 KB Output is correct
36 Correct 8 ms 6272 KB Output is correct
37 Correct 8 ms 6272 KB Output is correct
38 Correct 8 ms 6272 KB Output is correct
39 Correct 8 ms 6272 KB Output is correct
40 Correct 329 ms 23544 KB Output is correct
41 Correct 344 ms 24092 KB Output is correct
42 Correct 351 ms 24092 KB Output is correct
43 Correct 137 ms 16760 KB Output is correct
44 Correct 141 ms 16760 KB Output is correct
45 Correct 324 ms 24352 KB Output is correct
46 Correct 304 ms 23080 KB Output is correct
47 Correct 363 ms 23560 KB Output is correct
48 Correct 138 ms 16120 KB Output is correct
49 Correct 282 ms 23160 KB Output is correct
50 Correct 328 ms 23404 KB Output is correct
51 Correct 294 ms 23208 KB Output is correct