Submission #1130823

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130823		enzy	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	1364 ms	131412 KiB

commuter_pass

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e5+10;
const int inf=1e18+10;
vector<pair<int,int>>adj[maxn], aux[4*maxn];
int dist[maxn][4], n, d[4*maxn];
struct aresta{
    int a, b, c; 
};
void dijkstra(int x, int t){
    for(int i=1;i<=n;i++) dist[i][t]=inf;
    dist[x][t]=0;
    set<pair<int,int>>s;
    for(int i=1;i<=n;i++) s.insert({dist[i][t],i});
    while(!s.empty()){
        auto f=s.begin();
        int u=f->second;
        s.erase(f);
        for(auto p : adj[u]){
            int viz=p.first, w=p.second;
            if(dist[u][t]+w<dist[viz][t]){
                s.erase({dist[viz][t],viz});
                dist[viz][t]=dist[u][t]+w;
                s.insert({dist[viz][t],viz});
            }
        }
    }
}
void dijkstra(int x){
    for(int i=1;i<=4*n;i++) d[i]=inf;
    d[x]=0;
    set<pair<int,int>>s;
    for(int i=1;i<=4*n;i++) s.insert({d[i],i});
    while(!s.empty()){
        auto f=s.begin();
        int u=f->second;
        s.erase(f);
        for(auto p : aux[u]){
            int viz=p.first, w=p.second;
            if(d[u]+w<d[viz]){
                s.erase({d[viz],viz});
                d[viz]=d[u]+w;
                s.insert({d[viz],viz});
            }
        }
    }
}
signed main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int m, s, t, u, v; cin >> n >> m >> s >> t >> u >> v;
    vector<aresta>process;
    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});
        process.push_back({a,b,c});
        process.push_back({b,a,c});
    }
    dijkstra(s,0);
    dijkstra(t,1);
    for(auto p : process){
        int a=p.a, b=p.b, c=p.c;
        aux[a].push_back({b,c});
        aux[a+3*n].push_back({b+3*n,c});
        if(dist[a][0]+dist[a][1]==dist[t][0]){ // a está no caminho
            aux[a+n].push_back({b+3*n,c});
            aux[a+2*n].push_back({b+3*n,c});
        }
        if(dist[b][0]+dist[b][1]==dist[t][0]){ // b está no caminho
            aux[a].push_back({b+n,c});
            aux[a].push_back({b+2*n,c});
        }
        if(dist[a][0]+c+dist[b][1]==dist[t][0]){ // s->a->b->t
            aux[a+n].push_back({b+n,0});
        }
        if(dist[a][1]+c+dist[b][0]==dist[t][0]){ // t->a->b->s
            aux[a+2*n].push_back({b+2*n,0});
        }
    }
    if(dist[u][0]+dist[u][1]==dist[t][0]){
        aux[u].push_back({u+n,0});
        aux[u].push_back({u+2*n,0});
    }
    dijkstra(u);
    cout << min({d[v],d[v+n],d[v+2*n],d[v+3*n]}) << endl;
    return 0;
}

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