oj.uz

Submission #638765

# Submission time Handle Problem Language Result Execution time Memory
638765 2022-09-07T11:07:37 Z Ez0zIOVgTsSgT Commuter Pass (JOI18_commuter_pass) C++14
100 / 100
 309 ms 23324 KB 
#include<bits/stdc++.h>
using namespace std;

void DBG() { cerr << "]\n"; }
template<class H, class... T> void DBG(H h, T... t) {
    cerr << h; if(sizeof...(t)) cerr << ", ";
    DBG(t...);
}
#ifdef LOCAL
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define dbg(...) 0
#endif // LOCAL

#define FOR(i,a,b) for(int i = (a) ; i<(b) ; i++)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for(int i = (b)-1 ; i>=(a) ; i--)
#define R0F(i,a) ROF(i,0,a)
#define each(e,a) for(auto &e : (a))
#define sz(v) (int)(v).size()
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pb push_back
#define tcT template<class T
#define nl "\n"
#define fi first
#define se second

using ll = long long;
using vi = vector<int>;
using pi = pair<int,int>;
using str = string;
tcT> using pqg = priority_queue<T,vector<T>,greater<T>>;

void setIO(string NAME = "") {
    cin.tie(0)->sync_with_stdio(0);
    if(sz(NAME)) {
        freopen((NAME + ".inp").c_str(),"r",stdin);
        freopen((NAME + ".out").c_str(),"w",stdout);
    }
}

tcT> bool ckmin(T&a, const T&b) {
    return b < a ? a=b,1 : 0; }
tcT> bool ckmax(T&a, const T&b) {
    return b > a ? a=b,1 : 0; }

const int MOD = 1e9 + 7;
const ll INF = 1e18;

const int MX = 1e5+5;
int N, M, S, T, U, V;
vector<pi> adj[MX];
ll distS[MX], distT[MX], distU[MX], distV[MX], dp[MX];

ll ans = INF;

void dijkstra(int src, ll dist[]) {
    FOR(i,1,N+1) dist[i] = INF;
    pqg<pair<ll,int>> pq;
    pq.push({dist[src] = 0, src});
    while(!pq.empty()) {
        int u = pq.top().se;
        ll du = pq.top().fi;
        pq.pop();
        if(du > dist[u]) continue;
        each(ed, adj[u]) {
            int v = ed.fi; ll dv = du + ed.se;
            if(ckmin(dist[v], dv)) pq.push({dist[v], v});
        }
    }
}

void dfs(int u, bool fromT) {
    if(~dp[u]) return;
    if(distS[u] + distT[u] != distS[T]) {
        dp[u] = INF;
        return;
    }
    dp[u] = distV[u];
    each(ed, adj[u]) {
        int v = ed.fi;
        if(fromT ? distT[u] + ed.se != distT[v] : distS[u] + ed.se != distS[v]) continue;
        dfs(v, fromT);
        ckmin(dp[u], dp[v]);
    }
    ckmin(ans, dp[u] + distU[u]);
}

void solve() {
    cin >> N >> M >> S >> T >> U >> V;
    F0R(i, M) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].pb({v, w});
        adj[v].pb({u, w});
    }
    dijkstra(S, distS);
    dijkstra(T, distT);
    dijkstra(U, distU);
    dijkstra(V, distV);
    ans = distU[V];
    memset(dp, -1, sizeof dp);
    dfs(S, 0);
    memset(dp, -1, sizeof dp);
    dfs(T, 1);
    cout << ans << nl;
}

int main() {
    setIO();

    int t=1;
    //cin>>t;
    while(t-->0) {
        solve();
    }

    return 0;
}

Compilation message

commuter_pass.cpp: In function 'void setIO(std::string)':
commuter_pass.cpp:38:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |         freopen((NAME + ".inp").c_str(),"r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:39:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |         freopen((NAME + ".out").c_str(),"w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 244 ms 19056 KB Output is correct
2 Correct 239 ms 17468 KB Output is correct
3 Correct 259 ms 23324 KB Output is correct
4 Correct 223 ms 19000 KB Output is correct
5 Correct 247 ms 17304 KB Output is correct
6 Correct 245 ms 19088 KB Output is correct
7 Correct 253 ms 17160 KB Output is correct
8 Correct 250 ms 17344 KB Output is correct
9 Correct 238 ms 18204 KB Output is correct
10 Correct 183 ms 18088 KB Output is correct
11 Correct 109 ms 15072 KB Output is correct
12 Correct 245 ms 18020 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 258 ms 18816 KB Output is correct
2 Correct 265 ms 18960 KB Output is correct
3 Correct 264 ms 18396 KB Output is correct
4 Correct 257 ms 18792 KB Output is correct
5 Correct 264 ms 19328 KB Output is correct
6 Correct 255 ms 21524 KB Output is correct
7 Correct 272 ms 21580 KB Output is correct
8 Correct 261 ms 18992 KB Output is correct
9 Correct 264 ms 19264 KB Output is correct
10 Correct 309 ms 18640 KB Output is correct
11 Correct 112 ms 16652 KB Output is correct
12 Correct 259 ms 21648 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4564 KB Output is correct
2 Correct 2 ms 3452 KB Output is correct
3 Correct 2 ms 3412 KB Output is correct
4 Correct 13 ms 5588 KB Output is correct
5 Correct 8 ms 4540 KB Output is correct
6 Correct 3 ms 3540 KB Output is correct
7 Correct 3 ms 3500 KB Output is correct
8 Correct 3 ms 3648 KB Output is correct
9 Correct 2 ms 3540 KB Output is correct
10 Correct 8 ms 4480 KB Output is correct
11 Correct 2 ms 3412 KB Output is correct
12 Correct 3 ms 3412 KB Output is correct
13 Correct 2 ms 3452 KB Output is correct
14 Correct 3 ms 3412 KB Output is correct
15 Correct 2 ms 3540 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 244 ms 19056 KB Output is correct
2 Correct 239 ms 17468 KB Output is correct
3 Correct 259 ms 23324 KB Output is correct
4 Correct 223 ms 19000 KB Output is correct
5 Correct 247 ms 17304 KB Output is correct
6 Correct 245 ms 19088 KB Output is correct
7 Correct 253 ms 17160 KB Output is correct
8 Correct 250 ms 17344 KB Output is correct
9 Correct 238 ms 18204 KB Output is correct
10 Correct 183 ms 18088 KB Output is correct
11 Correct 109 ms 15072 KB Output is correct
12 Correct 245 ms 18020 KB Output is correct
13 Correct 258 ms 18816 KB Output is correct
14 Correct 265 ms 18960 KB Output is correct
15 Correct 264 ms 18396 KB Output is correct
16 Correct 257 ms 18792 KB Output is correct
17 Correct 264 ms 19328 KB Output is correct
18 Correct 255 ms 21524 KB Output is correct
19 Correct 272 ms 21580 KB Output is correct
20 Correct 261 ms 18992 KB Output is correct
21 Correct 264 ms 19264 KB Output is correct
22 Correct 309 ms 18640 KB Output is correct
23 Correct 112 ms 16652 KB Output is correct
24 Correct 259 ms 21648 KB Output is correct
25 Correct 8 ms 4564 KB Output is correct
26 Correct 2 ms 3452 KB Output is correct
27 Correct 2 ms 3412 KB Output is correct
28 Correct 13 ms 5588 KB Output is correct
29 Correct 8 ms 4540 KB Output is correct
30 Correct 3 ms 3540 KB Output is correct
31 Correct 3 ms 3500 KB Output is correct
32 Correct 3 ms 3648 KB Output is correct
33 Correct 2 ms 3540 KB Output is correct
34 Correct 8 ms 4480 KB Output is correct
35 Correct 2 ms 3412 KB Output is correct
36 Correct 3 ms 3412 KB Output is correct
37 Correct 2 ms 3452 KB Output is correct
38 Correct 3 ms 3412 KB Output is correct
39 Correct 2 ms 3540 KB Output is correct
40 Correct 274 ms 19452 KB Output is correct
41 Correct 234 ms 18244 KB Output is correct
42 Correct 225 ms 18128 KB Output is correct
43 Correct 135 ms 15668 KB Output is correct
44 Correct 134 ms 15708 KB Output is correct
45 Correct 233 ms 17320 KB Output is correct
46 Correct 232 ms 16660 KB Output is correct
47 Correct 226 ms 18920 KB Output is correct
48 Correct 108 ms 12624 KB Output is correct
49 Correct 194 ms 19104 KB Output is correct
50 Correct 239 ms 17108 KB Output is correct
51 Correct 227 ms 17048 KB Output is correct