제출 #882257

#제출 시각아이디문제언어결과실행 시간메모리
882257kokoueEvacuation plan (IZhO18_plan)C++14
41 / 100
4034 ms29352 KiB
#include<bits/stdc++.h> using namespace std; int n,m,k,q; bool is_npp[100001]; vector<pair<int,int>> edges[100001]; vector<long long> sp(100001,INT_MAX); vector<int> npp; void dijkstra() { priority_queue<pair<long long,int>> q; vector<long long> dist(n+1,INT_MAX); for(int i=0;i<npp.size();i++) { q.push({0,npp[i]}); dist[npp[i]]=0; sp[npp[i]]=0; } while(!q.empty()) { int curr=q.top().second; long long currDist=-q.top().first; q.pop(); if(dist[curr]<currDist) continue; for(auto edge:edges[curr]) { int next=edge.first; int weight=edge.second; if(dist[curr]+weight<dist[next]) { dist[next]=dist[curr]+weight; sp[next]=min(sp[next],dist[next]); q.push({-dist[next],next}); } } } } int dijkstra(int start,int finish) { priority_queue<pair<long long,int>> q; vector<long long> away(n+1,0); q.push({sp[start],start}); away[start]=sp[start]; while(!q.empty()) { int curr=q.top().second; long long currAway=q.top().first; q.pop(); if(away[curr]>currAway) continue; for(auto edge:edges[curr]) { int next=edge.first; long long len=sp[next]; if(away[next]<min(len,away[curr])) { away[next]=min(len,away[curr]); q.push({away[next],next}); } } } return away[finish]; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cin>>n>>m; int ai,bi,wi; for(int i=0;i<m;i++) { cin>>ai>>bi>>wi; edges[ai].push_back({bi,wi}); edges[bi].push_back({ai,wi}); } cin>>k; for(int i=0;i<k;i++) { int npp1; cin>>npp1; is_npp[npp1]=true; npp.push_back(npp1); } dijkstra(); cin>>q; int si,ti; for(int i=0;i<q;i++) { cin>>si>>ti; if(is_npp[si]==true || is_npp[ti]==true) {printf("0\n");continue;} printf("%lld\n",dijkstra(si,ti)); } }

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

plan.cpp: In function 'void dijkstra()':
plan.cpp:12:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |     for(int i=0;i<npp.size();i++)
      |                 ~^~~~~~~~~~~
plan.cpp: In function 'int main()':
plan.cpp:89:20: warning: format '%lld' expects argument of type 'long long int', but argument 2 has type 'int' [-Wformat=]
   89 |         printf("%lld\n",dijkstra(si,ti));
      |                 ~~~^    ~~~~~~~~~~~~~~~
      |                    |            |
      |                    |            int
      |                    long long int
      |                 %d
#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...