제출 #903864

#제출 시각아이디문제언어결과실행 시간메모리
903864pccRelay Marathon (NOI20_relaymarathon)C++14
25 / 100
2654 ms135672 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define pll pair<ll,ll> #define pii pair<int,int> #define fs first #define sc second #define tlll tuple<ll,ll,ll> #define tiii tuple<int,int,int> const int inf = 1e9+10; const int mxn = 1e5+10; vector<pii> paths[mxn]; vector<pii> dist[mxn]; priority_queue<tiii,vector<tiii>,greater<tiii>> pq; ll N,M,K; int sp[mxn]; vector<pair<int,pii>> v; void DIJKSTRA(){ for(int i = 1;i<=K;i++){ int now = sp[i]; dist[now].push_back(make_pair(0,now)); sort(dist[now].begin(),dist[now].end()); pq.push(make_tuple(0,now,now)); } while(!pq.empty()){ int d = get<0>(pq.top()),now = get<1>(pq.top()),f = get<2>(pq.top()); pq.pop(); bool flag = false; for(auto &i:dist[now]){ if(i == make_pair(d,f))flag = true; } if(!flag)continue; for(auto nxt:paths[now]){ if(dist[nxt.fs].size()<5||dist[nxt.fs].back().fs>=d+nxt.sc){ bool can = true; int idx = -1; for(int i = 0;i<dist[nxt.fs].size();i++){ if(dist[nxt.fs][i].sc == f){ if(dist[nxt.fs][i].fs<=d+nxt.sc)can = false; else idx = i; } } if(!can)continue; if(idx == -1){ dist[nxt.fs].push_back({d+nxt.sc,f}); } else{ dist[nxt.fs][idx].fs = d+nxt.sc; } sort(dist[nxt.fs].begin(),dist[nxt.fs].end()); pq.push(make_tuple(d+nxt.sc,nxt.fs,f)); while(dist[nxt.fs].size()>5)dist[nxt.fs].pop_back(); } } } return; } int main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin>>N>>M>>K; for(int i = 1;i<=M;i++){ int a,b,c; cin>>a>>b>>c; paths[a].push_back(make_pair(b,c)); paths[b].push_back(make_pair(a,c)); } for(int i = 1;i<=K;i++)cin>>sp[i]; DIJKSTRA(); /* for(int i = 1;i<=K;i++){ cout<<sp[i]<<":";for(auto &j:dist[sp[i]])cout<<j.fs<<','<<j.sc<<' ';cout<<endl; } */ for(int i = 1;i<=K;i++){ for(auto &j:dist[sp[i]]){ if(j.sc == sp[i])continue; v.push_back(make_pair(j.fs,make_pair(sp[i],j.sc))); } } sort(v.begin(),v.end()); for(auto &i:v){ if(min(i.sc.fs,i.sc.sc) != 1){ cout<<i.fs+1; return 0; } } }

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

RelayMarathon.cpp: In function 'void DIJKSTRA()':
RelayMarathon.cpp:41:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for(int i = 0;i<dist[nxt.fs].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...