oj.uz

답안 #330631

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
330631 2020-11-26T02:28:47 Z plourde27 Commuter Pass (JOI18_commuter_pass) C++17
100 / 100
 684 ms 31692 KB 
#include <iostream>
#include <string>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <algorithm>
#include <map>
#include <fstream>
#include <bitset>
#include <unordered_map>
#include <stack>
#include <list>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef map<int, int> mii;
typedef map<int, string> mis;
typedef map<string, int> msi;
typedef set<int> si;
typedef set<ll> sl;
typedef map<ll, ll> mll;
typedef queue<int> qi;
typedef queue<ii> qii;
typedef vector<string> vs;
typedef pair<ll, ll> iil;
typedef priority_queue<int> pqi;
typedef priority_queue<ii> pqii;
typedef priority_queue<ll> pqil;
typedef priority_queue<iil> pqiil;
typedef vector<iil> viil;
typedef vector<vi> vvi;
typedef long double ld;
typedef pair<int, ii> iii;
typedef pair<iil, ll> iiil;
typedef vector<pair<pair<int,int>,int> > viii;
typedef vector<pair<pair<ll,ll>,ll> > viiil;
typedef vector<vl> vvl;

#define pb push_back
#define mp make_pair
#define rep(i, n) for (int i = 0 ; i < n ; i++)
#define rrep(i, m, n) for (int i = m ; i < n ; i++)
#define per(i, n) for (int i = n - 1 ; i >= 0 ; i--)
#define perr(i, m, n) for (int i = n - 1 ; i >= m ; i--)
#define INF 2000000000
#define int long long

ll MOD = 1000000007;

viil adj[100005];
ll dpU[100005];
ll dpV[100005];
ll distU[100005];
ll distV[100005];
ll distS[100005];
ll tans;
bool vis[100005];
int n;

void dijkstra(int s, ll fill[]) {
    memset(vis, false, sizeof vis);
    
    priority_queue<pair<int, int>> q;
    q.push({0, s});
    
    while (q.size()) {
        iil inf = q.top();
        q.pop();
        
        ll vt = inf.second;
        ll ds = -inf.first;
        
        if (vis[vt]) continue;
        fill[vt] = ds;
        vis[vt] = true;
        
        for (ii a : adj[vt]) {
            q.push({-ds - a.second, a.first});
        }
    }
    
}

void dijkstra2(int s, int e) {
    rep(i, n) dpU[i] = 100000000000000000;
    rep(i, n) dpV[i] = 100000000000000000;
    memset(vis, false, sizeof vis);
    
    priority_queue<pair<int, pair<int, int>>> q;
    
    q.push({0, {s, -1}});
    
    while (q.size()) {
        pair<int, pair<int, int>> inf = q.top();
        q.pop();
        
        int ds = -inf.first;
        int vt = inf.second.first;
        int ls = inf.second.second;
        
        //cout << vt << " " << ds << endl;
        
        if (!vis[vt]) {
            vis[vt] = true;
            
            dpU[vt] = distU[vt];
            dpV[vt] = distV[vt];
            
            distS[vt] = ds;
            
            if (ls != -1) {
                dpU[vt] = min(dpU[vt], dpU[ls]);
                dpV[vt] = min(dpV[vt], dpV[ls]);
            }
            
            for (ii a : adj[vt]) {
                q.push({-ds - a.second, {a.first, vt}});
            }
        }
        else if (ds == distS[vt]) {
            if (min(dpU[ls], distU[vt]) + min(dpV[ls], distV[vt]) <= dpU[vt] + dpV[vt]) {
                dpU[vt] = min(dpU[ls], distU[vt]);
                dpV[vt] = min(dpV[ls], distV[vt]);
            }
        }
    }
    
    /*rep(i, n) cout << distV[i] << " ";
    cout << endl;
    
    rep(i, n) {
        cout << dpU[i] << " " << dpV[i] << endl;
    }
    cout << endl;*/
    
    tans = min(tans, dpU[e] + dpV[e]);
}

void solve() {
    //gen(10000, 20000);
    
    ll m;
    cin >> n >> m;
    
    ll s, t;
    cin >> s >> t;
    
    s--; t--;
    
    ll u, v;
    cin >> u >> v;
    
    u--; v--;
    
    rep(i, m) {
        int a, b, c;
        cin >> a >> b >> c;
        
        
        a--; b--;
        adj[a].pb({b, c});
        adj[b].pb({a, c});
    }
    
    
    dijkstra(u, distU);
    
    dijkstra(v, distV);
    
    tans = 100000000000000000;
    
    dijkstra2(s, t);
    dijkstra2(t, s);
    
    tans = min(tans, distU[v]);
    
    
    cout << tans << endl;
    
    
    
}

void querySolve() {
    int t;
    cin >> t;
    for (int i = 0 ; i < t ; i++) {
        solve();
    }
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    solve();
    //querySolve();
}

Subtask #1
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 684 ms 27520 KB Output is correct
2 Correct 549 ms 26796 KB Output is correct
3 Correct 565 ms 26364 KB Output is correct
4 Correct 658 ms 30192 KB Output is correct
5 Correct 559 ms 26660 KB Output is correct
6 Correct 636 ms 31036 KB Output is correct
7 Correct 559 ms 30196 KB Output is correct
8 Correct 605 ms 30460 KB Output is correct
9 Correct 652 ms 31664 KB Output is correct
10 Correct 621 ms 31692 KB Output is correct
11 Correct 173 ms 13932 KB Output is correct
12 Correct 637 ms 31608 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 596 ms 27264 KB Output is correct
2 Correct 546 ms 23128 KB Output is correct
3 Correct 562 ms 26568 KB Output is correct
4 Correct 555 ms 23388 KB Output is correct
5 Correct 539 ms 23152 KB Output is correct
6 Correct 581 ms 26348 KB Output is correct
7 Correct 569 ms 23020 KB Output is correct
8 Correct 553 ms 23308 KB Output is correct
9 Correct 559 ms 22928 KB Output is correct
10 Correct 557 ms 26368 KB Output is correct
11 Correct 172 ms 12012 KB Output is correct
12 Correct 572 ms 26452 KB Output is correct

Subtask #3
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 5628 KB Output is correct
2 Correct 3 ms 2924 KB Output is correct
3 Correct 3 ms 2924 KB Output is correct
4 Correct 85 ms 9096 KB Output is correct
5 Correct 47 ms 6984 KB Output is correct
6 Correct 4 ms 3052 KB Output is correct
7 Correct 5 ms 3180 KB Output is correct
8 Correct 7 ms 3252 KB Output is correct
9 Correct 4 ms 3052 KB Output is correct
10 Correct 42 ms 6848 KB Output is correct
11 Correct 2 ms 2796 KB Output is correct
12 Correct 3 ms 2796 KB Output is correct
13 Correct 3 ms 2924 KB Output is correct
14 Correct 4 ms 2924 KB Output is correct
15 Correct 3 ms 2924 KB Output is correct

Subtask #4
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 684 ms 27520 KB Output is correct
2 Correct 549 ms 26796 KB Output is correct
3 Correct 565 ms 26364 KB Output is correct
4 Correct 658 ms 30192 KB Output is correct
5 Correct 559 ms 26660 KB Output is correct
6 Correct 636 ms 31036 KB Output is correct
7 Correct 559 ms 30196 KB Output is correct
8 Correct 605 ms 30460 KB Output is correct
9 Correct 652 ms 31664 KB Output is correct
10 Correct 621 ms 31692 KB Output is correct
11 Correct 173 ms 13932 KB Output is correct
12 Correct 637 ms 31608 KB Output is correct
13 Correct 596 ms 27264 KB Output is correct
14 Correct 546 ms 23128 KB Output is correct
15 Correct 562 ms 26568 KB Output is correct
16 Correct 555 ms 23388 KB Output is correct
17 Correct 539 ms 23152 KB Output is correct
18 Correct 581 ms 26348 KB Output is correct
19 Correct 569 ms 23020 KB Output is correct
20 Correct 553 ms 23308 KB Output is correct
21 Correct 559 ms 22928 KB Output is correct
22 Correct 557 ms 26368 KB Output is correct
23 Correct 172 ms 12012 KB Output is correct
24 Correct 572 ms 26452 KB Output is correct
25 Correct 41 ms 5628 KB Output is correct
26 Correct 3 ms 2924 KB Output is correct
27 Correct 3 ms 2924 KB Output is correct
28 Correct 85 ms 9096 KB Output is correct
29 Correct 47 ms 6984 KB Output is correct
30 Correct 4 ms 3052 KB Output is correct
31 Correct 5 ms 3180 KB Output is correct
32 Correct 7 ms 3252 KB Output is correct
33 Correct 4 ms 3052 KB Output is correct
34 Correct 42 ms 6848 KB Output is correct
35 Correct 2 ms 2796 KB Output is correct
36 Correct 3 ms 2796 KB Output is correct
37 Correct 3 ms 2924 KB Output is correct
38 Correct 4 ms 2924 KB Output is correct
39 Correct 3 ms 2924 KB Output is correct
40 Correct 647 ms 30940 KB Output is correct
41 Correct 644 ms 31292 KB Output is correct
42 Correct 625 ms 31348 KB Output is correct
43 Correct 181 ms 14188 KB Output is correct
44 Correct 194 ms 14112 KB Output is correct
45 Correct 591 ms 25344 KB Output is correct
46 Correct 567 ms 25132 KB Output is correct
47 Correct 638 ms 26880 KB Output is correct
48 Correct 212 ms 13552 KB Output is correct
49 Correct 615 ms 29568 KB Output is correct
50 Correct 541 ms 25228 KB Output is correct
51 Correct 553 ms 25392 KB Output is correct