제출 #565783

#제출 시각아이디문제언어결과실행 시간메모리
565783DodoEvacuation plan (IZhO18_plan)C++14
22 / 100
4099 ms106280 KiB
#include <bits/stdc++.h> #define ll long long #define endl '\n' #define pb push_back using namespace std; const ll mx=100006; ll INF = 100000000000000008; ll n,m; vector<pair<ll,ll>>v[mx]; ll d[mx]; void dij(ll x) { ll dis[n+1]; for(int i=1;i<=n;i++)dis[i]=INF; bool st[n+1]={}; priority_queue<pair<ll,ll>, vector<pair<ll,ll>>, greater<pair<ll,ll>> > pq; dis[x]=0; ll cnt=0; pq.push({0,x}); while(cnt!=n) { while(st[pq.top().second])pq.pop(); cnt++; ll ve=pq.top().second; st[ve]=1; d[ve]=min(d[ve],dis[ve]); for(auto u:v[ve]) { if(st[u.first])continue; dis[u.first]=min(dis[u.first],dis[ve]+u.second); pq.push({dis[u.first],u.first}); } } } ll solve(ll a,ll b) { if(d[a]==0||d[b]==0)return 0; ll mn=d[a]; bool st[n+1]={}; priority_queue<pair<ll,ll>> pq; pq.push({mn,a}); while(st[b]==0) { while(st[pq.top().second])pq.pop(); ll ve=pq.top().second; st[ve]=1; mn=min(mn,d[ve]); for(auto u:v[ve]) { if(st[u.first])continue; pq.push({d[u.first],u.first}); } } return mn; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>n>>m; map<pair<ll,ll>,ll>mp; for(int i=1;i<=n;i++)d[i]=INF; while(m--) { ll a,b,w; cin>>a>>b>>w; v[a].push_back({b,w}); v[b].push_back({a,w}); mp[{a,b}]=1; mp[{b,a}]=1; } ll k; cin>>k; for(int i=0;i<k;i++) { ll x; cin>>x; dij(x); } ll q; cin>>q; while(q--) { ll a,b; cin>>a>>b; if(mp[{a,b}]||mp[{b,a}])cout<<min(d[a],d[b])<<endl; else cout<<solve(a,b)<<endl; } return 0; } /* 9 12 1 9 4 1 2 5 2 3 7 2 4 3 4 3 6 3 6 4 8 7 10 6 7 5 5 8 1 9 5 7 5 4 12 6 8 2 2 4 7 5 1 6 5 3 4 8 5 8 1 5 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...