Submission #1241916

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241916		khanhtt	Commuter Pass (JOI18_commuter_pass)	C++20	0 / 100	764 ms	327680 KiB

commuter_pass

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int n,m,s,t,u,v,Ls[100005],Lu[100005],Lv[100005],length=1e9;
vector<int> trace[100005],path;
vector<pair<int,int>> adj[100005];
vector<vector<int>> op;
void dijkstra(int start, int* L){
    for (int i=1; i<=n; i++) L[i]=1e9;
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
    L[start]=0;
    pq.push({0,start});
    while (!pq.empty()){
        auto [a,b]=pq.top();
        pq.pop();
        if (a>L[b]) continue;
        for (auto [nx,w]:adj[b]){
            if (a+w<L[nx]){
                L[nx]=a+w;
                trace[nx].clear();
                trace[nx].push_back(b);
                pq.push({L[nx],nx});
            }
            else if (a+w==L[nx]){
                trace[nx].push_back(b);
            }
        }
    }
}
void back(int a){
    path.push_back(a);
    if (a==s){
        op.push_back(path);
        path.pop_back();
        return;
    }
    for (int i:trace[a]){
        back(i);
    }
    path.pop_back();
}
main(){
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    cin >> n >> m >> s >> t >> u >> v;
    for (int i=1; i<=m; i++){
        int a,b,c; cin >> a >> b >> c;
        adj[a].push_back({b,c});
        adj[b].push_back({a,c});
    }
    dijkstra(s,Ls);
    // cout << Ls[t] << "\n";
    back(t);
    dijkstra(u,Lu);
    dijkstra(v,Lv);
    for (auto a:op){
        int k=1e9;
        for (int i=a.size()-1; i>=0; i--){
            k=min(k,Lv[a[i]]);
        }
        for (int i=a.size()-1; i>=0; i--){
            length=min(length,Lu[a[i]]+k);
        }
    }
    cout << length;
}

Compilation message (stderr)

commuter_pass.cpp:43:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   43 | main(){
      | ^~~~

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