oj.uz

답안 #597409

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
597409 2022-07-16T01:00:00 Z ljuba Commuter Pass (JOI18_commuter_pass) C++17
31 / 100
 753 ms 40812 KB 
#include <bits/stdc++.h>
#include <queue>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
 
typedef vector<int> vi;
typedef vector<ll> vll;
 
typedef vector<vi> vvi;
typedef vector<vll> vvll;
 
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
typedef vector<pii> vpii;
typedef vector<pll> vpll;
 
typedef vector<vpii> vvpii;
typedef vector<vpll> vvpll;
 
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x).size()
#define fi first
#define se second
 
template<class T> bool ckmin(T &a, const T &b) {return a > b ? a = b, 1 : 0;}
template<class T> bool ckmax(T &a, const T &b) {return a < b ? a = b, 1 : 0;}
 
namespace debug {
    void __print(int x) {cerr << x;}
    void __print(long long x) {cerr << x;}
    void __print(double x) {cerr << x;}
    void __print(long double x) {cerr << x;}
    void __print(char x) {cerr << '\'' << x << '\'';}
    void __print(const string &x) {cerr << '\"' << x << '\"';}
    void __print(const char *x) {cerr << '\"' << x << '\"';}
    void __print(bool x) {cerr << (x ? "true" : "false");}
 
    template<typename T, typename V>
    void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
    template<typename T>
    void __print(const T &x) {int f = 0; cerr << '{'; for(auto z : x) cerr << (f++ ? "," : ""), __print(z); cerr << "}";}
    void _print() {cerr << "]\n";}
    template <typename T, typename... V>
    void _print(T t, V... v) {__print(t); if(sizeof...(v)) cerr << ", "; _print(v...);}
 
#ifdef ljuba
#define dbg(x...) cerr << "\e[91m" << "LINE(" << __LINE__ << ") -> " << "[" << #x << "] = ["; _print(x)
#else
#define dbg(x...)
#endif
}
 
using namespace debug;
 
const char nl = '\n';
 
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
 
/*
“If you win, you live. If you lose, you die. If you don’t fight, you can’t win!”
― Eren Yaeger
*/
 
const ll INF = 1e18 + 12;
 
vector<array<int, 3>> nadjiSpecijalne(int n, int s, int t, const vector<array<int, 3>> &edges) {
    vector<vpll> adj(n);
    vll dist(n, INF);
 
    vvpii sa(n);
 
    for(auto &z : edges) {
        adj[z[0]].pb({z[1], z[2]});
        adj[z[1]].pb({z[0], z[2]});
    }
 
    priority_queue<pll, vpll, greater<>> pq;
    pq.push({0, s});
    dist[s] = 0;
 
    while(!pq.empty()) {
        auto tren = pq.top();
        pq.pop();
 
        if(dist[tren.se] != tren.fi) continue;

        dbg(tren.se, dist[tren.se]);
 
        for(auto e : adj[tren.se]) {
            if(ckmin(dist[e.fi], dist[tren.se] + e.se)) {
                pq.push({dist[e.fi], e.fi});
                sa[e.fi].clear();
                sa[e.fi].pb({tren.se, e.se});
            } else if(dist[e.fi] == dist[tren.se] + e.se) {
                sa[e.fi].pb({tren.se, e.se});
            }
        }
    }

    dbg(sa);
 
    vector<array<int, 3>> ans;
 
    set<int> trenutne;
    trenutne.insert(t);
 
    vector<bool> posetio(n, false);
 
    while(sz(trenutne)) {
        int tren = *trenutne.begin();
        //dbg(tren);
        trenutne.erase(tren);
        posetio[tren] = true;
 
        for(auto e : sa[tren]) {
            ans.pb({e.fi, tren, e.se});
            if(!posetio[e.fi]) {
                trenutne.insert(e.fi);
            }
        }
    }
 
    return ans;
}
 
ll dijkstra(int n, int s, int t, const vector<array<int, 3>> &edges) {
    vvpii adj(n);
    vll dist(n, INF);
 
    for(auto &z : edges) {
        adj[z[0]].pb({z[1], z[2]});
    }
 
    priority_queue<pll, vpll, greater<>> pq;
    pq.push({0, s});
    dist[s] = 0;
 
    while(!pq.empty()) {
        auto tren = pq.top();
        pq.pop();
 
        if(dist[tren.se] != tren.fi) continue;
 
        for(auto e : adj[tren.se]) {
            if(ckmin(dist[e.fi], dist[tren.se] + e.se)) {
                pq.push({dist[e.fi], e.fi});
            }
        }
    }
 
    return dist[t];
}
 
void solve() {
    int n, m;
    cin >> n >> m;
 
    int s, t, u, v;
    cin >> s >> t >> u >> v;
    --s, --t, --u, --v;
 
    vector<array<int, 3>> edges;
 
    for(int i = 0; i < m; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        --a, --b;
        edges.pb({a, b, c});
    }
 
    auto spec = nadjiSpecijalne(n, s, t, edges);

    for(auto z : spec) {
        dbg(z[0] + 1, z[1] + 1, z[2]);
    }
 
    auto ostale = spec;
    ostale.clear();
 
    {
        set<array<int, 3>> gas;
        for(auto z : spec) {
            gas.insert(z);
            gas.insert({z[1], z[0], z[2]});
        }
 
        for(auto z : edges) {
            if(gas.count(z)) continue;
            ostale.pb(z);
        }
    }
 
    auto sveee = edges;
    for(auto z : edges) {
        sveee.pb({z[1], z[0], z[2]});
    }
 
    vector<array<int, 3>> qwer;
    qwer = sveee;
 
    for(auto z : spec) {
        qwer.pb({z[0], z[1], 0});
        // qwer.pb({z[1], z[0], z[2]});
    }
 
    ll ans = dijkstra(n, u, v, qwer);
    ckmin(ans, dijkstra(n, v, u, qwer));
 
    qwer = sveee;
 
    for(auto z : spec) {
        // qwer.pb({z[0], z[1], z[2]});
        qwer.pb({z[1], z[0], 0});
    }
 
    ckmin(ans, dijkstra(n, u, v, qwer));
    ckmin(ans, dijkstra(n, v, u, qwer));
 
    cout << ans << nl;
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int testCases = 1;
    //cin >> testCases;
    while(testCases--)
        solve();
}

Compilation message

commuter_pass.cpp: In function 'void solve()':
commuter_pass.cpp:180:14: warning: variable 'z' set but not used [-Wunused-but-set-variable]
  180 |     for(auto z : spec) {
      |              ^

Subtask #1
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 498 ms 38712 KB Output is correct
2 Correct 528 ms 40280 KB Output is correct
3 Correct 630 ms 39008 KB Output is correct
4 Correct 476 ms 40136 KB Output is correct
5 Correct 628 ms 35252 KB Output is correct
6 Correct 501 ms 38172 KB Output is correct
7 Correct 667 ms 39548 KB Output is correct
8 Correct 577 ms 36312 KB Output is correct
9 Correct 500 ms 40236 KB Output is correct
10 Correct 380 ms 40272 KB Output is correct
11 Correct 276 ms 20984 KB Output is correct
12 Correct 495 ms 40268 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 567 ms 37720 KB Output is correct
2 Correct 567 ms 39920 KB Output is correct
3 Correct 611 ms 39896 KB Output is correct
4 Correct 542 ms 40004 KB Output is correct
5 Correct 674 ms 37972 KB Output is correct
6 Correct 653 ms 38248 KB Output is correct
7 Correct 753 ms 40812 KB Output is correct
8 Correct 623 ms 39660 KB Output is correct
9 Correct 600 ms 40040 KB Output is correct
10 Correct 626 ms 39724 KB Output is correct
11 Correct 323 ms 22100 KB Output is correct
12 Correct 647 ms 38236 KB Output is correct

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 4244 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 23 ms 6932 KB Output is correct
5 Correct 16 ms 3756 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Incorrect 3 ms 720 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 498 ms 38712 KB Output is correct
2 Correct 528 ms 40280 KB Output is correct
3 Correct 630 ms 39008 KB Output is correct
4 Correct 476 ms 40136 KB Output is correct
5 Correct 628 ms 35252 KB Output is correct
6 Correct 501 ms 38172 KB Output is correct
7 Correct 667 ms 39548 KB Output is correct
8 Correct 577 ms 36312 KB Output is correct
9 Correct 500 ms 40236 KB Output is correct
10 Correct 380 ms 40272 KB Output is correct
11 Correct 276 ms 20984 KB Output is correct
12 Correct 495 ms 40268 KB Output is correct
13 Correct 567 ms 37720 KB Output is correct
14 Correct 567 ms 39920 KB Output is correct
15 Correct 611 ms 39896 KB Output is correct
16 Correct 542 ms 40004 KB Output is correct
17 Correct 674 ms 37972 KB Output is correct
18 Correct 653 ms 38248 KB Output is correct
19 Correct 753 ms 40812 KB Output is correct
20 Correct 623 ms 39660 KB Output is correct
21 Correct 600 ms 40040 KB Output is correct
22 Correct 626 ms 39724 KB Output is correct
23 Correct 323 ms 22100 KB Output is correct
24 Correct 647 ms 38236 KB Output is correct
25 Correct 19 ms 4244 KB Output is correct
26 Correct 2 ms 340 KB Output is correct
27 Correct 2 ms 332 KB Output is correct
28 Correct 23 ms 6932 KB Output is correct
29 Correct 16 ms 3756 KB Output is correct
30 Correct 2 ms 468 KB Output is correct
31 Incorrect 3 ms 720 KB Output isn't correct
32 Halted 0 ms 0 KB -