Submission #1130207

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130207		enzy	Commuter Pass (JOI18_commuter_pass)	C++20	0 / 100	842 ms	43264 KiB

commuter_pass

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e5+10;
const int inf=1e15+10;
vector<pair<int,int>>adj[maxn];
vector<int>vim[maxn][4];
int dist[maxn][4], n, marc[maxn], aux[maxn]; 
//dist[i][?] 0-> dist a partir do u, 1-> dist a partir do v, 2-> dist a partir do s
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});
                vim[viz][t].clear();
            }
            if(dist[u][t]+w==dist[viz][t]) vim[viz][t].push_back(u);
        }
    }
}
void calc(int x, int t){
    memset(marc,0,sizeof(marc));
    queue<int>q;
    for(auto a : vim[x][t]){
        q.push(a);
        aux[a]=min(aux[a],aux[x]);
    }
    while(!q.empty()){
        int at=q.front(); q.pop();
        marc[at]++;
        for(auto a : vim[at][t]){
            if(marc[a]) continue;
            aux[a]=min({aux[a],aux[at]});
            q.push(a);
        }
    }
}
signed main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int m, s, t, u, v; 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(u,0);
    int resp=dist[v][0];
    dijkstra(v,1);
    dijkstra(s,2);
    dijkstra(t,3);
    for(int i=1;i<=n;i++) aux[i]=dist[i][1];
    calc(t,2);
    calc(s,3);
    int du=inf, dv=inf; 
    // no caso s=u, o u sempre perntence a commuter pass  sendo assim o custo será apenas o de v
    // chegar a qualquer possivel linha 
    for(int i=1;i<=n;i++){
        if(marc[i]){
            du=min(du,dist[i][0]);
            dv=min(dv,dist[i][1]);
        }
    }
    resp=dv;
    cout << resp << endl;
    return 0;
}// b

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