제출 #854374

#제출 시각아이디문제언어결과실행 시간메모리
854374Zero_OPCommuter Pass (JOI18_commuter_pass)C++14
100 / 100
212 ms21344 KiB
#include<bits/stdc++.h> using namespace std; template<class T> bool minimize(T& a, T b){ if(a>b) return a=b, true; return false; } template<class T> bool maximize(T& a, T b){ if(a<b) return a=b, true; return false; } #define range(v) begin(v), end(v) #define compact(v) v.erase(unique(range(v)), end(v)) typedef long long ll; typedef unsigned long long ull; const int N=1e5+5; int n, m; vector<pair<int, int>> g[N]; vector<int> par[N]; vector<ll> dijkstra(int st){ priority_queue<pair<ll, int>> pq; vector<ll> d(n, -1); d[st]=0; pq.push({0, st}); while(!pq.empty()){ ll cost; int u; tie(cost, u)=pq.top(); pq.pop(); if(-cost!=d[u]) continue; for(int i=0; i<g[u].size(); ++i){ int v, w; tie(v, w)=g[u][i]; if(d[v]==-1 or (d[v]>(d[u]+w))){ d[v]=d[u]+w; pq.push({-d[v], v}); } } } return d; } vector<ll> dijkstra_withTrace(int st){ vector<ll> d(n, -1); d[st]=0; priority_queue<pair<ll, int>> pq; pq.push({0, st}); while(!pq.empty()){ ll cost; int u; tie(cost, u)=pq.top(); pq.pop(); if(-cost!=d[u]) continue; for(int i=0; i<g[u].size(); ++i){ int v, w; tie(v, w)=g[u][i]; if(d[v]==-1 or (d[v]>d[u]+w)){ d[v]=d[u]+w; par[v].clear(); par[v].push_back(u); pq.push({-d[v], v}); } else if(d[v]==d[u]+w) par[v].push_back(u); } } return d; } void Zero_OP(){ int s, t, U, V; cin>>n>>m>>s>>t>>U>>V; --s, --t, --U, --V; while(m--){ int a, b, c; cin>>a>>b>>c; --a, --b; g[a].push_back({b, c}); g[b].push_back({a, c}); } vector<ll> dU=dijkstra(U), dV=dijkstra(V), dS=dijkstra_withTrace(s); ll ans=dU[V]; priority_queue<pair<ll, int>> pq; vector<ll> d(n, -1); d[t]=dV[t]; pq.push({-d[t], t}); while(!pq.empty()){ ll cost; int u; tie(cost, u)=pq.top(); pq.pop(); if(-cost!=d[u]) continue; minimize(ans, d[u]+dU[u]); for(int i=0; i<par[u].size(); ++i){ int v=par[u][i]; if(d[v]==-1 or (d[v]>min(d[u], dV[v]))){ d[v]=min(d[u], dV[v]); pq.push({-d[v], v}); } } } fill(range(d), -1); d[t]=dU[t]; pq.push({-d[t], t}); while(!pq.empty()){ ll cost; int u; tie(cost, u)=pq.top(); pq.pop(); if(-cost!=d[u]) continue; minimize(ans, d[u]+dV[u]); for(int i=0; i<par[u].size(); ++i){ int v=par[u][i]; if(d[v]==-1 or (d[v]>min(d[u], dU[v]))){ d[v]=min(d[u], dU[v]); pq.push({-d[v], v}); } } } cout<<ans; } int main(){ ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); Zero_OP(); return 0; }

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

commuter_pass.cpp: In function 'std::vector<long long int> dijkstra(int)':
commuter_pass.cpp:38:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |         for(int i=0; i<g[u].size(); ++i){
      |                      ~^~~~~~~~~~~~
commuter_pass.cpp: In function 'std::vector<long long int> dijkstra_withTrace(int)':
commuter_pass.cpp:61:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |         for(int i=0; i<g[u].size(); ++i){
      |                      ~^~~~~~~~~~~~
commuter_pass.cpp: In function 'void Zero_OP()':
commuter_pass.cpp:101:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |         for(int i=0; i<par[u].size(); ++i){
      |                      ~^~~~~~~~~~~~~~
commuter_pass.cpp:119:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |         for(int i=0; i<par[u].size(); ++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...