Submission #1155262

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155262		trandangquang	Commuter Pass (JOI18_commuter_pass)	C++20	0 / 100	2095 ms	19956 KiB

commuter_pass

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

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

const int N=100005;

int n,m,s,t,u,v; ll d[3][N],dp[N]; bool chk[N];
vector<ii> adj[N];
vector<int> dag[N];

void dijkstra(int st, int id){
    memset(d[id],0x3f,sizeof(d[id]));
    d[id][st]=0;
    priority_queue<ii,vector<ii>,greater<ii>>pq;
    pq.push({0,st});
    while(pq.size()){
        ii tp=pq.top();pq.pop();
        ll dx=tp.fi; int x=tp.se;
        if(dx>d[id][x]) continue;

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

void dfs(int x){
    dp[x]=d[2][x];
    for(int y:dag[x]){
        dfs(y);
        if(chk[y]) dp[x]=min(dp[x],dp[y]);
        chk[x]|=chk[y];
    }
}

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

    cin>>n>>m>>s>>t>>u>>v;
    for(int i=1; i<=m; ++i){
        int x,y,w; cin>>x>>y>>w;
        adj[x].emplace_back(y,w);
        adj[y].emplace_back(x,w);
    }

    dijkstra(s,0); dijkstra(u,1); dijkstra(v,2);
    for(int x=1; x<=n; ++x){
        for(ii e:adj[x]){
            int y=e.fi,w=e.se;
            if(d[0][y]==d[0][x]+w){
                dag[x].emplace_back(y);
            }
        }
    }

    chk[t]=1;
    dfs(s);
    ll res=1e18;
    for(int i=1; i<=n; ++i){
        res=min(res,d[1][i]+dp[i]);
    }
    cout<<res<<'\n';
}

Compilation message (stderr)

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

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