제출 #1087605

#제출 시각아이디문제언어결과실행 시간메모리
1087605shiori_chanCommuter Pass (JOI18_commuter_pass)C++17
15 / 100
2069 ms262144 KiB
#include<iostream> #include<vector> #include<queue> #include<cstring> #define int long long using namespace std; const int nd = 1e5 + 5 , INF = 1e15; vector<pair<int,int> > adj[nd]; vector<int>g[nd + 4] , in(nd + 5 , 0) , topo , f(nd + 4) , par[nd + 4]; priority_queue< pair<int , int> , vector< pair<int,int> > , greater< pair<int,int> > >q; bool vs[nd + 4]; vector< vector<int> > dis(5 , vector<int> (nd + 1 , INF)); void dijs(int r , int p){ q.push({0 , r}); dis[p][r] = 0; memset(vs , false , nd); while(!q.empty()){ int u = q.top().second , h = q.top().first; q.pop(); if(vs[u])continue; //cout << r << " " << h << " " << u <<" " << '\n'; vs[u] = true; for(auto v : adj[u])if(!vs[v.first]){ //cout << v.first << '\n'; if(h + v.second < dis[p][v.first]){ dis[p][v.first] = h + v.second , q.push({dis[p][v.first] , v.first}); } } } } void build(int u){ for(auto [v, vw] : adj[u]){ if(dis[0][u] == dis[0][v] + vw){ g[v].push_back(u); par[u].push_back(v); ++in[u]; build(v); } } } void bfs(int s){ queue<int> h; h.push(s); while(!h.empty()){ int u = h.front(); h.pop(); topo.push_back(u); for(int v : g[u]){ --in[v]; if(!in[v])h.push(v); } } } void solve(){ int n,m; int s ,t , x, y; cin >> n >> m; cin >> s >> t >> x >> y; for(int i = 1;i <= m; ++i){ int l , r ,w; cin >> l >> r >> w; adj[l].push_back({r , w}) , adj[r].push_back({l , w}); } dijs(s , 0) , dijs(t , 1) , dijs(x , 2) , dijs(y , 3); memset(vs , false , sizeof(vs)); build(t);bfs(s); //for(int i = 1;i <= n; ++i)cout << in[i] << '\n'; f[s] = dis[2][s]; int res = INF; for(int i = 1;i < topo.size(); ++i){ int u = topo[i]; f[u] = dis[2][u]; for(auto v : par[u]){ f[u] = min(f[u] , f[v]); } res = min(res , f[u] + dis[3][u]); } f[s] = dis[3][s]; res = min(res ,f[s] + dis[2][s]); for(int i = 1;i < topo.size(); ++i){ int u = topo[i]; f[u] = dis[3][u]; for(auto v : par[u]){ f[u] = min(f[u] , f[v]); } res = min(res , f[u] + dis[2][u]); } res = min(res , dis[2][y]); cout << res; } signed main(){ ios_base::sync_with_stdio(false);cin.tie(0); #define task "task" //freopen(task".inp","r",stdin);freopen(task".out","w",stdout); solve(); }

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

commuter_pass.cpp: In function 'void solve()':
commuter_pass.cpp:80:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |     for(int i = 1;i < topo.size(); ++i){
      |                   ~~^~~~~~~~~~~~~
commuter_pass.cpp:92:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |     for(int i = 1;i < topo.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...