oj.uz

Submission #946358

# Submission time Handle Problem Language Result Execution time Memory
946358 2024-03-14T14:24:11 Z vjudge1 Commuter Pass (JOI18_commuter_pass) C++17
24 / 100
 68 ms 16464 KB 
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("Ofast,unroll-loops,fast-math,O3")

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <cassert>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <fstream>
#include <unordered_map>
#define ll long long
#define int long long
#define all(v) v.begin(), v.end()
#define nl '\n'
#define pb push_back
#define sz(s) (int)(s).size()
#define f first
#define s second
using namespace std;
const ll N = 1e5 + 50, MX = 1e18;
bool was[N];
void solve(){
    ll n,m;
    cin >> n >> m;
    vector <pair <int, int> > g[n + 1];
    ll s, t, u, v;
    cin >> s >> t >> u >> v;
    for(int i = 1; i <= m; i++){
        ll a, b, x;
        cin >> a >> b >> x;
        g[a].pb({b,x});
        g[b].pb({a, x});
    }
    if(n <= 300) {
        ll d[n+1][n + 1];
        for(int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                d[i][j] = MX;
            }
        }
        for(int i = 1; i <= n; i++){
            for (int j = 1; j <= n; j++) {
                was[j] = 0;
            }
            d[i][i] = 0;
            priority_queue< pair<long long, int> > s;
            s.push({0, i});
            while(s.size() != 0) {
                int curv = s.top().second;
                s.pop();
                if(was[curv]) continue;
                was[curv] = 1;
                for(auto [to, w]: g[curv]) {
                    if(i == 6){
                        //cout << d[i][to] << ' ' << to << " " << w << " " << d[i][v] << " " << v << nl;
                    }
                    if(d[i][to] > d[i][curv] + w) {
                        //s.erase({d[to], to});
                        d[i][to] = d[i][curv] + w;
                        s.push({-d[i][to], to});
                    }
                }
            }
        }
        ll ans = d[u][v];
        //cout << d[s][t] << nl;
        //cout << ds[3] << " " << dt[5] << nl;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (d[s][i] + d[t][j] + d[i][j] == d[s][t] || d[s][j] + d[t][i] + d[i][j] == d[s][t]) {
                    ans = min(ans, d[u][i] + d[v][j]);
                }
            }
        }
        cout << ans << nl;
    }
}
signed main(){
    //freopen("lca.in", "r", stdin);
    //freopen("lca.out", "w", stdout);
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    ll ql=1;
    //cin >> ql;
    //tst++;
    while(ql--){
        solve();
    }
}

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 67 ms 16464 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 68 ms 16212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 2904 KB Output is correct
2 Correct 11 ms 1116 KB Output is correct
3 Correct 11 ms 1368 KB Output is correct
4 Correct 38 ms 4444 KB Output is correct
5 Correct 29 ms 2904 KB Output is correct
6 Correct 16 ms 1116 KB Output is correct
7 Correct 18 ms 1116 KB Output is correct
8 Correct 29 ms 1372 KB Output is correct
9 Correct 19 ms 1112 KB Output is correct
10 Correct 30 ms 2908 KB Output is correct
11 Correct 3 ms 1116 KB Output is correct
12 Correct 6 ms 1116 KB Output is correct
13 Correct 10 ms 1116 KB Output is correct
14 Correct 14 ms 1260 KB Output is correct
15 Correct 14 ms 1276 KB Output is correct

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 67 ms 16464 KB Output isn't correct
2 Halted 0 ms 0 KB -