제출 #1155827

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1155827		trandangquang	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	357 ms	25432 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);
    res=min(res,d[0][tl]);

    /// 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]);
    }
    ///

    /// DAG-Dijkstra from th
    dijkstra(th,2);
    for(int i=1; i<=n; ++i){
        dag[i].clear();
        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));
    memset(chk,0,sizeof(chk));
    memset(vis,0,sizeof(vis));
    chk[sh]=1;
    dfs(th);

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

    if(res==(ll)1e18) cout<<"-1\n";
    else 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();
}

컴파일 시 표준 에러 (stderr) 메시지

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

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