제출 #788553

#제출 시각아이디문제언어결과실행 시간메모리
788553prefixorsuuffiixxCommuter Pass (JOI18_commuter_pass)C++14
100 / 100
398 ms27852 KiB
//ashoori is my love //ashoori is my love//ashoori is my love//ashoori is my love//ashoori is my love//ashoori is my love #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef int it; typedef pair<ll, ll> pii; typedef pair<ll, pii> piii; #pragma GCC optimize ("O3") #pragma GCC target("avx2") #pragma GCC optimize("unroll-loops,Ofast") #define sep "\n" #define pes " " #define int long long #define print(x,n) for(int i=1; i<=n ; i++)cout<<x[i]<<" " #define scan(x,n) for(int i=1 ; i<=n ; i++)cin>>x[i] #define all(x) x.begin(), x.end() #define pb push_back #define F first #define Se second #define sz size #define cin2(r,j) cin>>r>>j #define cin1(r) cin>>r #define cin3(r,j,k) cin>>r>>j>>k # define InTheNameOfGod ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); const int maxx=1e5+1000; const ll MOD=1000000007; const ll inf=1e18; int S,T,U,V,n,m; vector<pii> g[maxx]; vector<ll> distances[maxx]; void dij(int v , int T) { vector<ll> ashoori(maxx-10); for(int i = 1 ; i <= n+10 ; i++)ashoori[i] = inf; priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>> pq; ashoori[v]=0; pq.push({0,v}); while(!pq.empty()){ int node = pq.top().Se; int ce = pq.top().F; pq.pop(); //if(ce!=ashoori[node])continue; for(auto U : g[node]){ if(ashoori[node] + U.Se < ashoori[U.F]){ ashoori[U.F] = ashoori[node] + U.Se; pq.push({ashoori[U.F],U.F}); } } } for(int i = 0 ; i <= n ; i++){ distances[T].pb(ashoori[i]); } } bool comp(int a,int b){ return distances[S][a]<distances[S][b]; } void solve(){ cin>>n>>m>>S>>T>>U>>V; for(int i = 1 ; i <= m ; i++){ int u , v , c; cin>>u>>v>>c; g[u].pb({v,c}); g[v].pb({u,c}); } dij(T , T); dij(S , S); dij(U , U ); dij(V , V); /*for(auto J : distances[V])cout<<J<<" "; cout<<"\n";*/ int answer = distances[U][V]; int mn[maxx]; for(int i = 0 ; i < maxx ; i++)mn[i] = inf; vector<int> nodes; for(int i = 1 ; i <= n ; i++){ if(distances[S][i] + distances[T][i] == distances[S][T])nodes.pb(i); } sort(all(nodes),comp); for(int i = 0 ; i < nodes.sz() ; i ++){ mn[nodes[i]] = distances[U][nodes[i]]; for(auto K : g[nodes[i]]){ mn[nodes[i]] = min(mn[nodes[i]] , mn[K.F]); } answer = min(mn[nodes[i]] + distances[V][nodes[i]],answer); } for(int i = 0 ; i < maxx ; i++)mn[i] = inf; for(int i = 0 ; i < nodes.sz() ; i ++){ mn[nodes[i]] = distances[V][nodes[i]]; for(auto K : g[nodes[i]]){ mn[nodes[i]] = min(mn[nodes[i]] , mn[K.F]); } answer = min(mn[nodes[i]] + distances[U][nodes[i]],answer); } cout<<answer; } /*===========================================================================================================================*/ signed main(){ //InTheNameOfGod; //int tt = clock(); //cout << fixed << setprecision(6); int tc = 1; //cin>>tc; //for(int i = 1 ; i <= 3 ; i++)cout<<dp[i]<<" "; while(tc--){solve(); //cerr << "TIME = " << clock() - tt << endl; //tt = clock(); } }

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

commuter_pass.cpp: In function 'void dij(long long int, long long int)':
commuter_pass.cpp:46:13: warning: unused variable 'ce' [-Wunused-variable]
   46 |         int ce = pq.top().F;
      |             ^~
commuter_pass.cpp: In function 'void solve()':
commuter_pass.cpp:102:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |     for(int i = 0 ; i < nodes.sz() ; i ++){
      |                     ~~^~~~~~~~~~~~
commuter_pass.cpp:112:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |     for(int i = 0 ; i < nodes.sz() ; i ++){
      |                     ~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...