제출 #1076654

#제출 시각아이디문제언어결과실행 시간메모리
1076654_no_nameCommuter Pass (JOI18_commuter_pass)C++17
100 / 100
184 ms20372 KiB
//Ai_2007 //Make the impossible possible #include<bits/stdc++.h> #define ll long long #define fo(i,m,n) for(int i=m; i<=n; i++) #define fod(i,m,n) for(int i=m; i>=n; i--) #define fi first #define se second #define Nmax 1000001 #define pb push_back #define pii pair<int,int> #define getbit(i,j) ((i>>j)&1) #define onbit(i,j) (i=(1<<j)) #define offbit(i,j) (i^=(1<<j)) #define pll pair<ll,ll> #define plp pair<ll,pii> using namespace std; const int N=1e5+5; int n,m,s,t,U,V; vector<pii> adj[N]; ll dis[2][N],ans,dp[2][N],d[N]; bool vst[N]; void dij1(int st, int id) { fo(i,1,n) { dis[id][i]=1e18; vst[i]=0; } dis[id][st]=0; priority_queue<pll, vector<pll>,greater<pll>> q; q.push({0,st}); while(!q.empty()){ int u=q.top().se; q.pop(); if(vst[u]) continue; vst[u]=1; for(auto it:adj[u]){ int v=it.fi; int w=it.se; if(dis[id][v] > dis[id][u] + w){ dis[id][v]=dis[id][u] + w; q.push({dis[id][v],v}); } } } } void dij2(int st, int en) { fo(i,0,n){ vst[i]=0; dp[0][i]=dp[1][i]=1e18; d[i]=1e18; } priority_queue<pll,vector<pll>,greater<pll>> q; d[st]=0; q.push({0,st}); dp[0][st]=dis[0][st]; dp[1][st]=dis[1][st]; while(!q.empty()){ int u=q.top().se; q.pop(); if(vst[u]) continue; vst[u]=1; for(auto it:adj[u]){ int v=it.fi; int w=it.se; if(d[v] > d[u] + w){ d[v]=d[u] + w; dp[0][v]=min(dis[0][v], dp[0][u]); dp[1][v]=min(dis[1][v], dp[1][u]); q.push({d[v],v}); } else if(d[v]==d[u]+w){ if(min(dis[0][v], dp[0][u]) + min(dis[1][v], dp[1][u])<dp[0][v] + dp[1][v]){ dp[0][v]=min(dis[0][v], dp[0][u]); dp[1][v]=min(dis[1][v], dp[1][u]); } } } } ans=min(ans, dp[0][en] + dp[1][en]); } void solve() { cin>>n>>m>>s>>t>>U>>V; fo(i,1,m){ int u,v,w; cin>>u>>v>>w; adj[u].pb({v,w}); adj[v].pb({u,w}); } dij1(U,0); dij1(V,1); ans=dis[0][V]; // ans=min(ans, dis[1][U]); dij2(s,t); // dij2(t,s); if(ans!=1e18) cout<<ans; else cout<<-1; } main() { //freopen("pathlib.inp","r",stdin); //freopen("pathlib.out","w",stdout); ios_base::sync_with_stdio(false); cin.tie(NULL); solve(); return 0; }

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

commuter_pass.cpp:101:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  101 | main()
      | ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...