제출 #501393

#제출 시각아이디문제언어결과실행 시간메모리
501393IOI_champion_in_1980Evacuation plan (IZhO18_plan)C++14
0 / 100
4010 ms17016 KiB
#include <bits/stdc++.h> #include <math.h> typedef long long ll; using namespace std; ll i, j, t, a, n, m, b, c, d, f, g, k, mmin; int x[100010], dis[100010]; vector <vector<pair<int, int>>> vc(100010); bool npp[100010], vis[100010], wis[100010]; queue<int> q; set<int> s; void mintap(int ind, int val) { if (vis[ind]) return; vis[ind]=true; s.insert(ind); if (npp[ind]) { mmin=val; return; } if (x[ind]!=0) { if (x[ind]+val<mmin) mmin=x[ind]+val; return; } for (int i=0; i<vc[ind].size(); i++) { int r=val+vc[ind][i].second; if (r<mmin) mintap(vc[ind][i].first, r); } } int main() { ios::sync_with_stdio(0); cin.tie(0); cin>>n>>m; for (a=1; a<=m; a++) { cin>>c>>d>>g; vc[c].push_back(make_pair(d, g)); vc[d].push_back(make_pair(c, g)); } // for (a=1; a<=n; a++) // { // cout<<a<<": "; // for (b=0; b<vc[a].size(); b++) // { // cout<<" { "<<vc[a][b].first<<" , "<<vc[a][b].second<<" } "; // } // cout<<endl; // } cin>>k; for (a=1; a<=k; a++) { cin>>c; x[c]=0; npp[c]=1; } for (a=1; a<=n; a++) { if (npp[a]) continue; mmin=INT_MAX; for (auto b:s) vis[b]=0; s.clear(); mintap(a, 0); x[a]=mmin; } // for (a=1; a<=n; a++) cout<<a<<") "<<x[a]<<endl; cin>>t; for (a=1; a<=t; a++) { cin>>c>>d; int ans=INT_MIN; for (b=1; b<=n; b++) { dis[b]=INT_MAX; wis[b]=0; } dis[c] = x[c]; wis[c] = true; q.push(c); while (!q.empty()) { int ss = q.front(); q.pop(); for (auto u : vc[ss]) { int p=u.first; if (wis[p]) continue; if (p!=d) { wis[p]=true; dis[p] = min(x[p], dis[ss]); q.push(p); continue; } else { // cout<<min(dis[ss], x[d])<<" "; ans=max(ans, min(dis[ss], x[d])); } } } cout<<min(ans, min(x[c], x[d]))<<endl; } } /* 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 */

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

plan.cpp: In function 'void mintap(int, int)':
plan.cpp:26:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |  for (int i=0; i<vc[ind].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...
#Verdict Execution timeMemoryGrader output
Fetching results...