제출 #1086309

#제출 시각아이디문제언어결과실행 시간메모리
1086309kiethm07Commuter Pass (JOI18_commuter_pass)C++11
31 / 100
227 ms31396 KiB
#include <bits/stdc++.h> #define pii pair<int,int> #define pli pair<long long,int> #define iii pair<int,pii> #define fi first #define se second #define vi vector<int> #define vii vector<pii> #define pb(i) push_back(i) #define all(x) x.begin(),x.end() #define TEXT "a" using namespace std; typedef long long ll; typedef unsigned long long ull; typedef long double ld; const ll inf = 1e15 + 5; const ld eps = 1e-8; const double pi = acos(-1); const int N = 1e5 + 5; vector<pii> a[N]; vector<int> b[N], c[N]; vector<ll> dS, dT, dX, dY; ll f[N], g[N]; int n,m; int s,t,x,y; void dijkstra(int s, vector<ll>& d){ d.resize(n + 5,inf); priority_queue<pli,vector<pli>,greater<pli>> pq; d[s] = 0; pq.push(pli(0,s)); while(!pq.empty()){ int u = pq.top().se; ll dis = pq.top().fi; pq.pop(); if (dis > d[u]) continue; for (int i = 0; i < a[u].size(); i++){ int v = a[u][i].fi; int w = a[u][i].se; if (d[u] + w < d[v]){ d[v] = d[u] + w; pq.push(pli(d[v],v)); } } } } void buildGraph(){ for (int u = 1; u <= n; u++){ for (int i = 0; i < a[u].size(); i++){ int v = a[u][i].fi; int w = a[u][i].se; if (dS[v] == dS[u] + w && dS[t] == dS[u] + w + dT[v]){ b[u].push_back(v); c[v].push_back(u); //cout << u << " " << v << " " << w << "\n"; } } } } void cal(int u){ if (f[u] != inf) return; f[u] = dX[u]; g[u] = dY[u]; for (int v : c[u]){ cal(v); f[u] = min(f[u], f[v]); g[u] = min(g[u], g[v]); } } void calR(int u){ if (f[u] != inf) return; f[u] = dX[u]; g[u] = dY[u]; for (int v : b[u]){ calR(v); f[u] = min(f[u], f[v]); g[u] = min(g[u], g[v]); } } int main(){ cin.tie(0) -> sync_with_stdio(0); if (fopen(TEXT".inp","r")){ freopen(TEXT".inp","r",stdin); freopen(TEXT".out","w",stdout); } cin >> n >> m; cin >> s >> t >> x >> y; for (int i = 1; i <= m; i++){ int u,v,w; cin >> u >> v >> w; a[u].pb(pii(v,w)); a[v].pb(pii(u,w)); } dijkstra(s, dS); dijkstra(t, dT); buildGraph(); swap(x,y); dijkstra(x, dX); dijkstra(y, dY); for (int i = 1; i <= n; i++) f[i] = g[i] = inf; cal(t); ll res = dX[y]; for (int i = 1; i <= n; i++){ res = min(res, f[i] + g[i]); } for (int i = 1; i <= n; i++) f[i] = g[i] = inf; calR(s); for (int i = 1; i <= n; i++){ res = min(res, f[i] + g[i]); } cout << res << "\n"; return 0; }

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

commuter_pass.cpp: In function 'void dijkstra(int, std::vector<long long int>&)':
commuter_pass.cpp:44:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |         for (int i = 0; i < a[u].size(); i++){
      |                         ~~^~~~~~~~~~~~~
commuter_pass.cpp: In function 'void buildGraph()':
commuter_pass.cpp:57:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |         for (int i = 0; i < a[u].size(); i++){
      |                         ~~^~~~~~~~~~~~~
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:94:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |         freopen(TEXT".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:95:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |         freopen(TEXT".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...