Submission #1273290

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273290		nlhuy	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	207 ms	20200 KiB

commuter_pass

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

#define ll long long
#define fi first
#define se second
#define Task "test"

typedef pair<ll,int>ii;

const int MOD = 1e9+7;
const ll INF = 1e17+7;
const int Maxn = 1e5+7;
const int di[] = {0, 0, -1, 1};
const int dj[] = {-1, 1, 0, 0};

int n,m,u,v,s,t;
ll dp[Maxn][2],distU[Maxn],distV[Maxn],dist[Maxn];
vector<ii>g[Maxn];

void dijkstra(int s,ll dp[]){
    for(int i=1;i<=n;i++) dp[i]=INF;
    dp[s]=0;
    priority_queue<ii,vector<ii>,greater<ii>>q;
    q.push({0,s});
    while(!q.empty()){
        int u=q.top().se;
        ll val=q.top().fi;
        q.pop();
        if (dp[u]<val) continue;
        for(ii x:g[u]){
            int v=x.fi,w=x.se;
            if (dp[v]>dp[u]+1LL*w){
                dp[v]=dp[u]+1LL*w;
                q.push({dp[v],v});
            }
        }
    }
}
ll calc(int s,int t){
    for(int i=1;i<=n;i++){
        dp[i][0]=dp[i][1]=dist[i]=INF;
    }
    priority_queue<ii,vector<ii>,greater<ii>>q;
    q.push({0,s});
    dist[s]=0;
    dp[s][0]=distU[s];
    dp[s][1]=distV[s];
    while(!q.empty()){
        int u=q.top().se;
        ll val=q.top().fi;
        q.pop();
        if (dist[u]<val) continue;
        for(ii x:g[u]){
            int v=x.fi,w=x.se;
            if (dist[v]>dist[u]+1LL*w){
                dist[v]=dist[u]+1LL*w;
                dp[v][0]=min(dp[u][0],distU[v]);
                dp[v][1]=min(dp[u][1],distV[v]);
                q.push({dist[v],v});
            }
            else if (dist[v]==dist[u]+1LL*w){
                if (dp[v][0]+dp[v][1]>min(dp[u][0],distU[v])+min(dp[u][1],distV[v])){
                    dp[v][0]=min(dp[u][0],distU[v]);
                    dp[v][1]=min(dp[u][1],distV[v]);
                    q.push({dist[v],v});
                }
            }
        } 
    }
    return dp[t][0]+dp[t][1];
}
void run_case(){
    cin>>n>>m>>s>>t>>u>>v;
    while(m--){
        int u,v,w;
        cin>>u>>v>>w;
        g[u].push_back({v,w});
        g[v].push_back({u,w});
    }
    dijkstra(u,distU);
    dijkstra(v,distV);
    ll ans=distU[v];
    ans=min(ans,min(calc(s,t),calc(t,s)));
    cout<<ans;
}
int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    if (fopen(Task ".inp", "r"))
    {
        freopen(Task ".inp", "r", stdin);
        freopen(Task ".out", "w", stdout);
    }
    int t = 1;
    //cin >> t;
    while(t--){
        run_case();
    }
}

Compilation message (stderr)

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

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