제출 #499044

#제출 시각아이디문제언어결과실행 시간메모리
499044KarabasanCommuter Pass (JOI18_commuter_pass)C++17
0 / 100
286 ms21356 KiB
#include <bits/stdc++.h> #define ll long long #define fast1 ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); #define endl "\n" #define int long long using namespace std; #pragma GCC optimize("Ofast") #pragma GCC target("fma,sse,sse2,sse3,avx") #pragma GCC optimize("unroll-loops") int n,m; int dizi[100005]; int s,e; int u,y; vector<pair<int,int> > v[100005]; int st[100005]; int en[100005]; int vis[100005]; void solve() { cin>>n>>m>>s>>e>>u>>y; for(int i=0;i<m;i++) { int a,b,c; cin>>a>>b>>c; v[a].push_back({-c,b}); v[b].push_back({-c,a}); } priority_queue<pair<int,int> > pq; pq.push({0,e}); while(!pq.empty()) { int x=pq.top().second; int yol=pq.top().first; pq.pop(); if(vis[x]) continue; vis[x]=1; en[x]=yol; for(int i=0;i<v[x].size();i++) { if(!vis[v[x][i].second]) pq.push({yol+v[x][i].first,v[x][i].second}); } } memset(vis,0,sizeof vis); while(!pq.empty()) pq.pop(); pq.push({0,s}); while(!pq.empty()) { int x=pq.top().second; int yol=pq.top().first; pq.pop(); if(vis[x]) continue; vis[x]=1; st[x]=yol; for(int i=0;i<v[x].size();i++) { if(!vis[v[x][i].second]) pq.push({yol+v[x][i].first,v[x][i].second}); } } memset(vis,0,sizeof vis); priority_queue<pair<pair<int,int>,pair<int,int> > >q; if(st[u]+en[u]!=st[e]) q.push({{0,0},{u,0}}); else q.push({{0,0},{u,1}}); while(!q.empty()) { int x=q.top().second.first; int yol=q.top().first.first; int ktr=q.top().second.second; int ata=q.top().first.second; q.pop(); if(vis[x]) continue; vis[x]=1; if(x==y) { cout<<-yol<<endl; return; } for(int i=0;i<v[x].size();i++) { if(!vis[v[x][i].second]) { //cout<<v[x][i].second<<" "<<st[v[x][i].second]<<" "<<st[x]<<" "<<st[ata]<<endl; if(ktr==2) q.push({{yol+v[x][i].first,x},{v[x][i].second,2}}); else if((st[v[x][i].second]+en[v[x][i].second]!=st[e]||st[x]+en[x]!=st[e])&&ktr==0) q.push({{yol+v[x][i].first,x},{v[x][i].second,0}}); else if((st[v[x][i].second]+en[v[x][i].second]!=st[e]||st[x]+en[x]!=st[e])&&ktr==1) q.push({{yol+v[x][i].first,x},{v[x][i].second,2}}); else if(((st[v[x][i].second]>st[x]&&st[ata]>st[x])||(st[v[x][i].second]<st[x]&&st[ata]<st[x]))&&ata!=0&&ktr==1) q.push({{yol,x},{v[x][i].second,2}}); else q.push({{yol,x},{v[x][i].second,1}}); } } } } signed main() { fast1 //freopen ("lca.gir","r",stdin); //freopen ("lca.cik","w",stdout); int t=1; //cin>>t; while(t--) { solve(); } return 0; }

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

commuter_pass.cpp: In function 'void solve()':
commuter_pass.cpp:40:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         for(int i=0;i<v[x].size();i++)
      |                     ~^~~~~~~~~~~~
commuter_pass.cpp:59:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |         for(int i=0;i<v[x].size();i++)
      |                     ~^~~~~~~~~~~~
commuter_pass.cpp:85:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |         for(int i=0;i<v[x].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...