제출 #718336

#제출 시각아이디문제언어결과실행 시간메모리
718336tigarCommuter Pass (JOI18_commuter_pass)C++14
31 / 100
397 ms28968 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; ll INF=LONG_LONG_MAX; ll m, n, s, t, u, v; vector<pair<ll, ll> >graff[200010]; vector<ll>dag[200010]; bool check1[200010], check2[200010]; ll distu[200010], distv[200010], dists[200010], distt[200010]; ll res=INF; void dijkstra(ll cvor, ll *dist) { for(int i=0; i<100010; i++){check1[i]=false; dist[i]=INF;} priority_queue<pair<ll, ll> >ord; dist[cvor]=0; ord.push({0, cvor}); while(!ord.empty()) { int cv=ord.top().second; ord.pop(); if(check1[cv])continue; check1[cv]=true; for(int j=0; j<graff[cv].size(); j++) { ll pp=graff[cv][j].first; dist[pp]=min(dist[pp], dist[cv]+graff[cv][j].second); if(!check1[pp])ord.push({-dist[pp], pp}); } } } void dfs1(ll prosli, ll cvor) { if(check2[cvor])return; check2[cvor]=true; if(dists[cvor]+distt[cvor]!=dists[t])return; dag[prosli].push_back(cvor); if(cvor==t)return; for(int i=0; i<graff[cvor].size(); i++) { if(dists[cvor]+graff[cvor][i].second+distt[graff[cvor][i].first]==dists[t])dfs1(cvor, graff[cvor][i].first); } return; } void dfs2(ll cvor, ll minv, ll minu) { minv=min(minv, distv[cvor]); minu=min(minu, distu[cvor]); res=min(res, minv+minu); if(cvor==t)return; for(int i=0; i<dag[cvor].size(); i++) { dfs2(dag[cvor][i], minv, minu); } return; } int main() { ios_base::sync_with_stdio(false); cin.tie(); cout.tie(); cin>>n>>m; cin>>s>>t; cin>>u>>v; ll a, b, c; for(int i=0; i<m; i++) { cin>>a>>b>>c; graff[a].push_back({b, c}); graff[b].push_back({a, c}); } dijkstra(u, distu); dijkstra(v, distv); dijkstra(s, dists); dijkstra(t, distt); dists[0]=0; dfs1(0, s); dfs2(s, INF, INF); cout<<min(res, distv[u]); return 0; }

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

commuter_pass.cpp: In function 'void dijkstra(ll, ll*)':
commuter_pass.cpp:26:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |         for(int j=0; j<graff[cv].size(); j++)
      |                      ~^~~~~~~~~~~~~~~~~
commuter_pass.cpp: In function 'void dfs1(ll, ll)':
commuter_pass.cpp:43:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for(int i=0; i<graff[cvor].size(); i++)
      |                  ~^~~~~~~~~~~~~~~~~~~
commuter_pass.cpp: In function 'void dfs2(ll, ll, ll)':
commuter_pass.cpp:56:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     for(int i=0; i<dag[cvor].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...