제출 #880395

#제출 시각아이디문제언어결과실행 시간메모리
880395alicanyazCommuter Pass (JOI18_commuter_pass)C++14
100 / 100
379 ms35780 KiB
#pragma GCC optimize("Ofast","unroll-loops") #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #include <ext/pb_ds/detail/standard_policies.hpp> using namespace std; using namespace __gnu_pbds; typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ost; #define endl "\n" #define ll long long #define ull unsigned long long #define ld long double #define pi pair<int,int> #define pll pair<long long,long long> #define vi vector<int> #define vll vector<long long> #define vpi vector<pair<int,int>> #define vpll vector<pair<long long,long long>> #define vvi vector<vector<int>> #define vvll vector<vector<long long>> #define vr vector<range<int>> #define cd complex<double> #define pb push_back void frd(string s){ freopen((s+".in").c_str(),"r",stdin); freopen((s+".out").c_str(),"w",stdout); } template<typename T> struct matrix{ vector<T> mtx; T Tdef; int column=-1,row=-1; matrix() {} matrix(int r,int c) { mtx.assign(r*c,Tdef); row = r; column = c; } matrix(int r,int c,T val){ mtx.assign(r*c,val); row = r; column = c; } struct proxy{ matrix *m ; int i; proxy(matrix* x , int y) : m(x) , i(y){} T &operator[] (int j){ return (m->mtx[i*(m->row) + j]); } }; proxy operator[](int i){ return proxy(this,i); } void fill(T x){for(auto &y:mtx)y=x;} void fill_row(int rw,T x,int l=0,int r=-1){ if(r==-1)r = column-1; for(int i=l;i<=r;i++){ mtx[rw*row + i] = x; } } void fill_column(int cl,T x,int l=0,int r=-1){ if(r == -1)r = row-1; for(int i=l;i<=r;i++){ mtx[i*row + cl] = x; } } void inc_row(int rw,T x,int l=0,int r=-1){ if(r==-1)r = column-1; for(int i=l;i<=r;i++){ mtx[rw*row + i] += x; } } void inc_column(int cl,T x,int l=0,int r=-1){ if(r == -1)r = row-1; for(int i=l;i<=r;i++){ mtx[i*row + cl] +=x; } } int count(int rw,T x,int l=0,int r=-1){ if(r == -1)r = column-1; int cnt = 0; for(int i=l;i<=r;i++)cnt += (mtx[rw*row + i] == x); return cnt; } }; template<typename V,typename S> istream& operator >> (istream &x,pair<V,S> &p){cin >> p.first >> p.second ;return x;} template<typename V,typename S> ostream& operator << (ostream &x,const pair<V,S> &p){cout << p.first <<" "<<p.second;return x;} #define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL) #define abs(x) ((x)>0?(x):-((x))) #define fr(i,j) for(int i=0;i<j;i++) #define frt(a,b,c) for(int a=b;a<c;a++) #define fra(x,y) for(auto &x:y) #define min(a,b) ((a)<(b)?(a):(b)) #define all(x) x.begin(),x.end() int mlog(int x) { return 32 - __builtin_clz(x) - 1; } ll sum(ll a,ll b,ll M=1e+9+7){ a%=M;b%=M;return (a+b)%M; } ll subs(ll a,ll b,ll M=1e+9+7){ a-=b;a%=M;if(a<0)a+=M;return a; } ll mult(ll a,ll b,ll M=1e+9+7){ a%=M;b%=M;return (a*b)%M; } ll bp(ll a,ll b,ll M=1e+9+7){ if(b == 0)return 1; if(b == 1)return a; ll x = bp(a,b/2,M); x = mult(x,x,M); if(b%2)x=mult(x,a,M); return x; } #define int ll #define MAXN 200005 const ll INF = 1e+16 + 2323231; vector<vpi> adj; array<int,MAXN> vis; array<ll,MAXN> U_dj , V_dj , S_dj , UDP , VDP , DP; //vll U_dj , V_dj , S_dj; vvll sp; void djikstra(array<ll,MAXN> &A,int st){ A[st] = 0; set<pll> sst;sst.insert({0,st}); while(sst.size()){ auto it = *(sst.begin()); sst.erase(sst.begin()); for(auto &x:adj[it.second]){ if(A[x.first] > A[it.second] + x.second){ sst.erase({A[x.first],x.first}); A[x.first] = A[it.second] + x.second; sst.insert({A[x.first],x.first}); } } } } ll ans; void djikstra2(int V,int en){ fill(all(vis),0); fill(all(UDP),INF);fill(all(VDP),INF); fill(all(S_dj),INF); S_dj[V]=0; UDP[V] = U_dj[V];VDP[V] = V_dj[V]; set<pll> sst;sst.insert({0,V}); while(sst.size()){ auto it = *(sst.begin()); sst.erase(sst.begin()); for(auto &x:adj[it.second]){ if(S_dj[x.first] == S_dj[it.second] + x.second){ ll MF = min(UDP[it.second],U_dj[x.first]); ll NF = min(VDP[it.second],V_dj[x.first]); if(MF + NF < UDP[x.first] + VDP[x.first]){ UDP[x.first] = MF; VDP[x.first] = NF; } } if(S_dj[x.first] > S_dj[it.second] + x.second){ sst.erase({S_dj[x.first],x.first}); S_dj[x.first] = S_dj[it.second] + x.second; sst.insert({S_dj[x.first],x.first}); UDP[x.first] = min(UDP[it.second],U_dj[x.first]); VDP[x.first] = min(VDP[it.second],V_dj[x.first]); } } } ans = min(ans,VDP[en]+UDP[en]); } int32_t main(){ fastio; int N,M;cin>>N>>M; adj.assign(N,vpi(0));sp.assign(N,vll(0)); fill(all(vis),0);fill(all(U_dj),INF);fill(all(V_dj),INF);fill(all(S_dj),INF);fill(all(VDP),INF);fill(all(UDP),INF);fill(all(DP),INF); int S,T,V,U;cin>>S>>T>>V>>U;S--;T--;V--;U--; fr(i,M){ int a,b;ll c;cin>>a>>b>>c;a--;b--; adj[a].pb({b,c}); adj[b].pb({a,c}); } djikstra(U_dj,U); djikstra(V_dj,V); ans = V_dj[U]; djikstra2(S,T); djikstra2(T,S); cout << ans << endl; }

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

commuter_pass.cpp: In function 'void frd(std::string)':
commuter_pass.cpp:25:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |     freopen((s+".in").c_str(),"r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:26:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |     freopen((s+".out").c_str(),"w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...