Submission #597409

#	Time	Username	Problem	Language	Result	Execution time	Memory
597409		ljuba	Commuter Pass (JOI18_commuter_pass)	C++17	31 / 100	753 ms	40812 KiB

commuter_pass

#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 (stderr)

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 / 16
• Subtask 2: 15 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 45