Submission #678602

#	Time	Username	Problem	Language	Result	Execution time	Memory
678602		vjudge1	Commuter Pass (JOI18_commuter_pass)	C++17	24 / 100	34 ms	1892 KiB

commuter_pass

#include<bits/stdc++.h>
using namespace std;

#define f first
#define s second

typedef long long ll;
typedef long double ld;
typedef pair<int, pair<int, int>> ft;

const ld PI = acos(-1);
const int maxn = 3e3+5;
const ll inf = 1e18;
const int mod = 998244353;

int n, m, S, T, U, V;

ll ans = inf, stp;

ll ds[maxn], du[maxn], dv[maxn], dps[2][maxn], dpt[2][maxn];

int deg1[maxn], deg2[maxn], ing[maxn];

vector<pair<int, int>> graph[maxn];
vector<int> g1[maxn], g2[maxn];

void dijkstra(ll *d, int vt){
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
    for(int i = 1; i <= n; i++){
        d[i]=inf;
    }
    d[vt]=0;
    pq.push({0, vt});
    while(!pq.empty()){
        auto x = pq.top();
        //cout << x.f << "\n";
        pq.pop();
        if(d[x.s] < x.f)continue;
        for(auto v: graph[x.s]){
            if(x.f + v.s < d[v.f]){
                d[v.f] = x.f+v.s;
                pq.push({d[v.f], v.f});
            }
        }
    }
}

signed main(){
    cin >> n >> m >> S >> T >> U >> V;
    while(m--){
        int a, b, w;
        cin >> a >> b >> w;
        graph[a].push_back({b, w});
        graph[b].push_back({a, w});
    }
    dijkstra(ds, S);
    dijkstra(du, U);
    dijkstra(dv, V);
    queue<int> q;
    q.push(T);
    while(!q.empty()){
        auto x = q.front();
        q.pop();
        if(ing[x])continue;
        ing[x]=1;
        for(auto v: graph[x]){
            if(ds[v.f] + v.s == ds[x]){
                g1[v.f].push_back(x);
                g2[x].push_back(v.f);
                deg1[x]++;
                deg2[v.f]++;
                q.push(v.f);
            }
        }
    }
    for(int i = 1; i <= n; i++){
        dps[0][i] = dpt[0][i] = du[i];
        dps[1][i] = dpt[1][i] = dv[i];
    }
    q.push(S);
    while(!q.empty()){
        auto x = q.front();
        q.pop();
        for(auto v: g1[x]){
            dps[0][v] = min(dps[0][v], dps[0][x]);
            dps[1][v] = min(dps[1][v], dps[1][x]);
            deg1[v]--;
            if(!deg1[v])q.push(v);
        }
    }
    q.push(T);
    while(!q.empty()){
        auto x = q.front();
        q.pop();
        for(auto v: g1[x]){
            dpt[0][v] = min(dpt[0][v], dpt[0][x]);
            dpt[1][v] = min(dpt[1][v], dpt[1][x]);
            deg2[v]--;
            if(!deg2[v])q.push(v);
        }
    }
    ans = du[V];
    for(int i = 1; i <= n; i++){
        if(ing[i]){
            ans = min({ans, dps[0][i]+dpt[1][i], dps[1][i]+dpt[0][i]});
            //cout << i << "\n";
        }
    }
    cout << ans;
}
 

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