Submission #448939

#	Time	Username	Problem	Language	Result	Execution time	Memory
448939		JovanB	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	584 ms	27520 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef long double ld;
 
int n;
ll dist[3][100005];
 
const ll INF = 1000000000000000LL;
 
vector <pair <int, int>> graf[100005];
 
void dij(int gde, int root){
    for(int i=1; i<=n; i++) dist[gde][i] = INF;
    dist[gde][root] = 0;
    set <pair <ll, int>> q;
    q.insert({0, root});
    while(!q.empty()){
        int v = q.begin()->second;
        q.erase(q.begin());
        for(auto c : graf[v]){
            if(dist[gde][c.first] > dist[gde][v]+c.second){
                q.erase({dist[gde][c.first], c.first});
                dist[gde][c.first] = c.second + dist[gde][v];
                q.insert({dist[gde][c.first], c.first});
            }
        }
    }
}
 
ll mn1[100005];
ll mn2[100005];
vector <int> gr[100005];
int ka[200005];
int kb[200005];
ll kc[200005];
int deg[200005];
 
int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout.precision(10);
    cout << fixed;
 
    int m;
    cin >> n >> m;
    int s1, t1, s2, t2;
    cin >> s1 >> t1 >> s2 >> t2;
    for(int i=1; i<=m; i++){
        int a, b, c;
        cin >> a >> b >> c;
        graf[a].push_back({b, c});
        graf[b].push_back({a, c});
        ka[i] = a;
        kb[i] = b;
        kc[i] = c;
    }
    dij(1, s1);
    dij(2, t1);
    for(int i=1; i<=m; i++){
        if(dist[1][ka[i]] > dist[1][kb[i]]) swap(ka[i], kb[i]);
        if(dist[1][t1] != dist[1][ka[i]] + kc[i] + dist[2][kb[i]]) continue;
        gr[kb[i]].push_back(ka[i]);
        deg[ka[i]]++;
    }
    dij(1, s2);
    dij(2, t2);
    queue <int> q;
    for(int i=1; i<=n; i++){
        mn1[i] = mn2[i] = INF;
        if(!deg[i]) q.push(i);
    }
    ll res = dist[1][t2];
    while(!q.empty()){
        int v = q.front();
        q.pop();
        res = min(res, mn1[v] + dist[2][v]);
        res = min(res, mn2[v] + dist[1][v]);
        mn1[v] = min(mn1[v], dist[1][v]);
        mn2[v] = min(mn2[v], dist[2][v]);
        for(auto c : gr[v]){
            deg[c]--;
            mn1[c] = min(mn1[c], mn1[v]);
            mn2[c] = min(mn2[c], mn2[v]);
            if(!deg[c]) q.push(c);
        }
    }
    cout << res << "\n";
    return 0;
}

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