Submission #1282838

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282838		smileyboi	Commuter Pass (JOI18_commuter_pass)	C++20	0 / 100	173 ms	25092 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using pii = pair<int,int>;
using pil = pair<int,ll>;
using pli = pair<ll,int>;
using pll = pair<ll,ll>;

#define __SmileyBoi__ int main()
#define __CodeKhongBug__ ios_base::sync_with_stdio(0);cin.tie(0);
#define all(v) v.begin(),v.end()
#define eb emplace_back

const int MAXN = 1e5 + 5;
const int MAXM = 2e5 + 5;
const ll INF = 2e18;

int n;
vector<pii> e1[MAXN],e2[MAXN];
ll da[MAXN],db[MAXN],dc[MAXN];

void dijkstra(int s,ll d[],vector<pii> e[]){
    priority_queue<pli,vector<pli>,greater<>> pq;
    fill(d + 1,d + n + 1,INF);
    d[s] = 0;
    pq.emplace(d[s],s);
    while(pq.size()){
        pii p = pq.top();pq.pop();
        ll dist = p.first,u = p.second;
        if(d[u] != dist) continue;
        for(pii t : e[u]){
            int v = t.first,w = t.second;
            if(d[v] > d[u] + w){
                d[v] = d[u] + w;
                pq.emplace(d[v],v);
            }
        }
    }
}

struct Edge{
    int u,v,w;
};

Edge edge[MAXM];

__SmileyBoi__{
    __CodeKhongBug__

    int m,a,b,c,d;
    cin >> n >> m >> a >> b >> c >> d;
    for(int i = 1;i <= m;i++){
        int u,v,w;
        cin >> u >> v >> w;
        e1[u].eb(v,w);
        e1[v].eb(u,w);
        edge[i] = {u,v,w};
    }
    dijkstra(a,da,e1);
    dijkstra(b,db,e1);
    ll dist = da[b];
    for(int i = 1;i <= m;i++){
        int u = edge[i].u,v = edge[i].v,w = edge[i].w;
        if(da[u] + w + db[v] == dist || da[v] + w + db[u] == dist){
            e2[u].eb(v,0);
            e2[v].eb(u,0);
        }
        else{
            e2[u].eb(v,w);
            e2[v].eb(u,w);
        }
    }
    dijkstra(c,dc,e2);
    cout << dc[d];
}

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