Submission #1265399

#TimeUsernameProblemLanguageResultExecution timeMemory
1265399hitsuujCommuter Pass (JOI18_commuter_pass)C++20
0 / 100
2095 ms18872 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define pb push_back #define lc 2*pos #define rc 2*pos+1 #define pii pair<int,int> #define fi first #define se second //CEK ENDL DAN INT LL #define endl '\n' #define inf 1e18 #define ti tuple<int,int,int> #define meekucaon ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); const int mod=1e9+7; int sf(int a){return (a%mod+mod)%mod;} int kal(int a,int b){return (sf(a)*sf(b))%mod;} int tam(int a,int b){return (sf(a)+sf(b))%mod;} int kur(int a,int b){return (sf(a)+mod-sf(b))%mod;} int inv(int a){ if(a<=1) return 1; return mod-(int)(mod/a)*inv(mod%a)%mod; } int bag(int a,int b){return kal(sf(a),inv(b));} const int lim=100000; int dis[5][lim+10]; vector<pii>g[lim+10]; int n,m,s,t,a,b; int nodso(int u,int v,int w){ if((dis[0][u]+w==dis[0][v]) && (dis[1][u]==dis[1][v]+w)) return 1; if((dis[0][v]+w==dis[0][u])&& (dis[1][v]==dis[1][u]+w)) return 1; return 0; } void dji(int ta,int st){ priority_queue<pii>q; q.push({0,st}); dis[ta][st]=0; while(q.size()){ auto [d,u]=q.top(); q.pop(); if(dis[ta][u]<d) continue; for(auto [v,w]:g[u]){ if(dis[ta][u]+w>=dis[ta][v]) continue; dis[ta][v]=dis[ta][u]+w; q.push({dis[ta][v],v}); } } } int vis[lim+10]; int dp[lim+10]; signed main(){ meekucaon cin>>n>>m>>s>>t>>a>>b; int dp[2][n+10]; for(int i=1;i<=n;i++){ dp[0][i]=inf; dp[1][i]=inf; for(int j=0;j<4;j++){ dis[j][i]=inf; } } for(int i=1;i<=m;i++){ int u,v,w;cin>>u>>v>>w; g[u].pb({v,w}); g[v].pb({u,w}); } dji(0,s);dji(1,t);dji(2,a);dji(3,b); queue<int>q; q.push(s); int ans=dis[3][a]; while(q.size()){ int u=q.front(); q.pop(); vis[u]=1; dp[0][u]=min(dp[0][u],dis[2][u]); dp[1][u]=min(dp[1][u],dis[3][u]); ans=min(ans,dp[0][u]+dp[1][u]); for(auto [v,w]:g[u]){ if(vis[v]) continue; if(nodso(u,v,w)){ vis[v]=1; dp[0][v]=min(dp[0][u],dp[0][v]); dp[1][v]=min(dp[1][u],dp[1][v]); q.push(v); } } } cout<<ans; } // 1. pasti dp // obs // 1. kalau masuk dalam shortest path bebas masuk keluar mana aja // 2. save smallest dari suatu node ke s,t,a,b // // subsoal // // (1 & 2) // // kalau masi masuk shortest path = 0 // // (3) // // N<=300 // // tiap shortest route x all // subtask 3 // n*n*n cek apakah ij dalam satu lane if yes then take min // how to make it in m/n
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...