Submission #698947

#	Time	Username	Problem	Language	Result	Execution time	Memory
698947		RandomLB	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	318 ms	39740 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef pair<ll, pi> E;
#define pb push_back
#define siz(x) (int)x.size()
#define ms(x, a) memset(x, a, sizeof(x))
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values){
    cout << vars << " = ";
    string delim = "";
    (...,(cout << delim << values, delim = ", "));
    cout << endl;
}
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
//===========================================
const int MAX = 1e5+5;
vector<pll> adj[MAX];
vector<int> pp[MAX], adj2[MAX], radj[MAX];
ll dis[MAX], dis2[4][MAX];
bool vis[MAX];

int main(){
    cin.tie(0)->sync_with_stdio(0);
    int n, m; cin >> n >> m;
    int s, t, src, tar;
    cin >> s >> t >> src >> tar;
    for (int i = 1; i <= m; i++){
        int a, b, w; cin >> a >> b >> w;
        adj[a].pb({b, w});
        adj[b].pb({a, w});
    }
    ms(dis, 0x3f3f3f3f);
    ms(dis2, 0x3f3f3f3f);
    priority_queue<pll, vector<pll>, greater<pll>> pq;
    pq.push({dis[s] = 0, s});
    while (siz(pq)){
        auto[d, v] = pq.top(); pq.pop();
        if (d != dis[v]) continue;
        for (auto[u, w]: adj[v]){
            if (dis[u] > dis[v]+w){
                pq.push({dis[u] = dis[v]+w, u});
                pp[u] = {v};
            } else if (dis[u] == dis[v]+w) pp[u].pb(v);
        }
    }
    //for (int i = 1; i <= n; i++) deb(i, dis[i]);
    queue<int> q;
    vis[t] = true; q.push(t);
    while (siz(q)){
        int v = q.front(); q.pop();
        for (int u: pp[v]){
            adj2[v].pb(u);
            radj[u].pb(v);
            if (!vis[u]){ vis[u] = true; q.push(u); }
        }
    }
    priority_queue<E, vector<E>, greater<E>> q2;
    q2.push({dis2[0][src] = 0, {0, src}});
    while (siz(q2)){
        auto[d, x] = q2.top(); q2.pop();
        auto[i, v] = x;
        if (v == tar){ cout << d << "\n"; return 0; }
        if (d != dis2[i][v]) continue;
        for (auto[u, w]: adj[v]){
            int ni = (!i? 0 : 3);
            if (dis2[ni][u] > dis2[i][v]+w){
                q2.push({dis2[ni][u] = dis2[i][v]+w, {ni, u}});
            }
        }
        if (!i || i == 1){
            for (int u: adj2[v]){
                if (dis2[1][u] > dis2[i][v]){
                    q2.push({dis2[1][u] = dis2[i][v], {1, u}});
                }
            }
        }
        if (!i || i == 2){
            for (int u: radj[v]){
                if (dis2[2][u] > dis2[i][v]){
                    q2.push({dis2[2][u] = dis2[i][v], {2, u}});
                }
            }
        }
    }
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:46:26: warning: narrowing conversion of 'v' from 'std::tuple_element<1, std::pair<long long int, long long int> >::type' {aka 'long long int'} to 'int' [-Wnarrowing]
   46 |                 pp[u] = {v};
      |                          ^
commuter_pass.cpp:46:26: warning: narrowing conversion of 'v' from 'std::tuple_element<1, std::pair<long long int, long long int> >::type' {aka 'long long int'} to 'int' [-Wnarrowing]

• Subtask 1: 16 / 16
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 45 / 45