Submission #488235

#TimeUsernameProblemLanguageResultExecution timeMemory
488235levsog2004Evacuation plan (IZhO18_plan)C++14
23 / 100
1384 ms71916 KiB
#include <iostream> #include <iomanip> #include <fstream> #include <algorithm> #include <cstring> #include <string> #include <vector> #include <queue> #include <deque> #include <stack> #include <cmath> #include <list> #include <set> #include <map> using namespace std; typedef int ll; #define all(x) x.begin(),x.end() #define al(a,n) (a,a+n) #define se second #define fr first #define m_p make_pair const ll N = 100005; const ll mod = 1000 * 1000 * 1000 + 7; const ll inf = 1000000009; ll n, m, k, z, t, x, y, ans, pat, a[N],c[N],dist[N],color[N]; vector<pair<ll, ll>> g[N]; map <ll, ll> mp[N]; pair<ll, ll> p; void dfs(int v, int u, int pow) { color[v] = 1; if (v == y) { pat = max(pat, pow); return; } for (int i = 0; i < g[v].size(); ++i) { if (g[v][i].first != u && color[g[v][i].first]==0) { dfs(g[v][i].first, v, min(pow, dist[g[v][i].first])); } } } int main() { cin >> n >> m; for (int i = 0; i < m; ++i) { cin >> x >> y >> z; mp[x][y] = 1; mp[y][x] = 1; g[x].push_back({ y,z }); g[y].push_back({ x,z }); } cin >> k; priority_queue<pair<ll, ll>> q; for (int i = 0; i <= n; ++i) dist[i] = inf; for (int i = 0; i < k; ++i) { cin >> a[i]; q.push({ 0,a[i] }); dist[a[i]] = 0; c[a[i]] = 1; } while (q.size() > 0) { p = q.top(); q.pop(); x = p.first*-1; y = p.second; for (int i = 0; i < g[y].size(); ++i) { if (dist[g[y][i].first] > x + g[y][i].second) { q.push({-1*(x+g[y][i].second),g[y][i].first}); dist[g[y][i].first] = x + g[y][i].second; } } } cin >> ans; for (int i = 0; i < ans; ++i) { cin >> x >> y; if (mp[x][y]!=1) { pat = -1; for (int j = 0; j <= n; ++j) { color[j] = 0; } color[x] = 1; dfs(x, x, dist[x]); cout << pat << endl; } else cout << min(dist[x], dist[y]) << endl; } return 0; }

Compilation message (stderr)

plan.cpp: In function 'void dfs(int, int, int)':
plan.cpp:37:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |  for (int i = 0; i < g[v].size(); ++i)
      |                  ~~^~~~~~~~~~~~~
plan.cpp: In function 'int main()':
plan.cpp:75:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |   for (int i = 0; i < g[y].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...
#Verdict Execution timeMemoryGrader output
Fetching results...