Submission #1155820

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155820		trandangquang	Commuter Pass (JOI18_commuter_pass)	C++20	0 / 100	213 ms	21488 KiB

commuter_pass

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

#define ll long long
#define ii pair<int,int>
#define li pair<ll,int>
#define fi first
#define se second
#define eb emplace_back

const int N=1e5+5;

int n,m,sh,th,sl,tl; ll d[3][N],dp[N],res=1e18; bool chk[N],vis[N];
vector<ii> adj[N];
vector<int> dag[N];

void dijkstra(int s, int i){
    memset(d[i],0x3f,sizeof(d[i]));
    d[i][s]=0;

    priority_queue<li,vector<li>,greater<li>> pq;
    pq.push({d[i][s],s});

    while(pq.size()){
        li tp=pq.top(); pq.pop();
        ll du=tp.fi,u=tp.se;
        if(du>d[i][u]) continue;

        for(ii e:adj[u]){
            int v=e.fi,w=e.se;
            if(d[i][v]>d[i][u]+w){
                d[i][v]=d[i][u]+w;
                pq.push({d[i][v],v});
            }
        }
    }
}

void dfs(int u){
    vis[u]=1;
    for(int v:dag[u]) if(!vis[v]){
        dfs(v);
        dp[u]=min(dp[u],dp[v]);
        chk[u]|=chk[v];
    }
    if(chk[u]) dp[u]=min(dp[u],d[1][u]);
}

void solve(){
    cin>>n>>m>>sh>>th>>sl>>tl;
    for(int i=1; i<=m; ++i){
        int u,v,w; cin>>u>>v>>w;
        adj[u].eb(v,w);
        adj[v].eb(u,w);
    }
    dijkstra(sl,0); dijkstra(tl,1); dijkstra(sh,2);

    /// DAG-Dijkstra from sh
    for(int i=1; i<=n; ++i){
        for(ii e:adj[i]){
            int j=e.fi,w=e.se;
            if(d[2][j]==d[2][i]+w){
                dag[i].eb(j);
            }
        }
    }

    memset(dp,0x3f,sizeof(dp));
    chk[th]=1;
    dfs(sh);

    for(int i=1; i<=n; ++i){
        res=min(res,d[0][i]+dp[i]);
    }
    cout<<res<<'\n';
}

int main(){
    if(fopen("test.inp","r")){
        freopen("test.inp","r",stdin);
        freopen("test.out","w",stdout);
    }
    cin.tie(0)->sync_with_stdio(0);

    solve();
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:80:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |         freopen("test.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:81:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |         freopen("test.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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