제출 #1108424

#제출 시각아이디문제언어결과실행 시간메모리
1108424KasymKEvacuation plan (IZhO18_plan)C++17
0 / 100
2 ms3064 KiB
#include "bits/stdc++.h" using namespace std; #define ff first #define ss second #define all(v) v.begin(), v.end() #define ll long long #define pb push_back #define pii pair<int, int> #define pli pair<ll, int> #define pll pair<ll, ll> #define tr(i, c) for(auto i = c.begin(); i != c.end(); ++i) #define wr puts("----------------") template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;} template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;} const int N = 1e5+5; const int INF = 1e9; vector<pii> adj[N]; int dis[N]; bool vis[N]; int main(){ freopen("file.txt", "r", stdin); int n, m; scanf("%d%d", &n, &m); for(int i = 1; i <= n; ++i) dis[i] = INF; for(int i = 1; i <= m; ++i){ int a, b, c; scanf("%d%d%d", &a, &b, &c); adj[a].pb({b, c}); adj[b].pb({a, c}); } int k; scanf("%d", &k); priority_queue<pii, vector<pii>, greater<pii>> pq; for(int i = 1; i <= k; ++i){ int x; scanf("%d", &x); dis[x] = 0; pq.push({0, x}); } while(!pq.empty()){ int x = pq.top().ss, val = pq.top().ff; pq.pop(); if(dis[x] != val) continue; tr(it, adj[x]){ int a = it->ff, w = it->ss; if(umin(dis[a], dis[x]+w)) pq.push({dis[a], a}); } } int a1, a2; auto check = [&](int ad) -> bool { for(int i = 1; i <= n; ++i) vis[i] = 0; queue<int> q; q.push(a1); vis[a1] = 1; while(!q.empty()){ int x = q.front(); q.pop(); tr(it, adj[x]){ if(it->ff==a2) return 1; if(!vis[it->ff] and dis[it->ff]>=ad) vis[it->ff] = 1, q.push(it->ff); } } return 0; }; int Q, same; scanf("%d", &Q); same = Q; while(Q--){ int s, t; scanf("%d%d", &s, &t); a1 = s, a2 = t; if(same==1 or n<=20){ int l = 0, r = 1e9, answer = 1e9; while(l <= r){ int mid = (l+r)>>1; if(check(mid)) l = mid+1, answer = mid; else r = mid-1; } printf("%d\n", min({answer, dis[s], dis[t]})); continue; } printf("%d\n", min(dis[s], dis[t])); } return 0; }

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

plan.cpp: In function 'int main()':
plan.cpp:22:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |     freopen("file.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
plan.cpp:24:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |     scanf("%d%d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~
plan.cpp:29:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |         scanf("%d%d%d", &a, &b, &c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
plan.cpp:34:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |     scanf("%d", &k);
      |     ~~~~~^~~~~~~~~~
plan.cpp:38:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |         scanf("%d", &x);
      |         ~~~~~^~~~~~~~~~
plan.cpp:73:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |     scanf("%d", &Q);
      |     ~~~~~^~~~~~~~~~
plan.cpp:77:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |         scanf("%d%d", &s, &t);
      |         ~~~~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...