제출 #338046

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
338046		iulia2100	Evacuation plan (IZhO18_plan)	C++14	41 / 100	4059 ms	84436 KiB

plan

#include <iostream>
#include <vector>
#include <queue>
#include <map>

using namespace std;

//ifstream cin ("labirint.in");
//ofstream cout ("labirint.out");

int n, m;
int a[100005], comp[100005];

vector <int> G[100005], p;
map <int, int> dist[100005];

namespace initial  {
  bool viz[100005];
  vector <pair <int, int>> v[100005];
  priority_queue <pair <int, int> > pq;

  void dijkstra()  {
    pair <int, int> nod;

    while (!pq.empty())  {
      nod = pq.top();
      pq.pop();
      if (a[nod.second] < - nod.first)
        continue;
      for (auto it : v[nod.second])  {
        if (viz[it.first] && a[nod.second] + it.second > a[it.first])
          continue;
        viz[it.first] = true;
        a[it.first] = a[nod.second] + it.second;
        pq.push({-a[it.first], it.first});
      }
    }
  }

  void solve()  {
    cin >> n >> m;
    int x, y, w, k;
    for (int i = 1; i <= m; ++i)  {
      cin >> x >> y >> w;
      v[x].push_back({y, w});
      v[y].push_back({x, w});
      G[x].push_back(y);
      G[y].push_back(x);
    }
    cin >> k;
    for (int i = 1; i <= k; ++i)  {
      cin >> x;
      pq.push({0, x});
      viz[x] = true;
    }
    dijkstra();
  }
}

namespace select_points  {
  bool viz[100005];

  void dfs(int nod, int x)  {
    viz[nod] = true;
    comp[nod] = x;
    for (auto it : G[nod])  {
      if (viz[it] || a[it] == 0)
        continue;
      dfs(it, x);
    }
  }

  int aux;
  bool ok[100005];

  void dijkstra(int nod, int k)  {
    priority_queue <pair <int, int> > pq;

    pq.push({a[nod], nod});
    dist[nod][k] = a[nod];

    while (!pq.empty())  {
      nod = pq.top().second;
      if (dist[nod][k] != pq.top().first)  {
        pq.pop();
        continue;
      }
      if (dist[nod][k] == a[nod])  {
        if (ok[nod])  {
          pq.pop();
          continue;
        }
        ok[nod] = true;
      }
      pq.pop();
      for (auto it : G[nod])  {
        if (dist[it][k] >= min(dist[nod][k], a[it]) || a[it] == 0 || ok[it])
          continue;
        dist[it][k] = min(dist[nod][k], a[it]);
        pq.push({dist[it][k], it});
      }
    }
  }

  void select_points()  {
    int componenta = 0;
    for (int i = 1; i <= n; ++i)  {
      if (!viz[i])  {
        if (a[i] == 0)  {
          comp[i] = 0;
          continue;
        }
        ++componenta;
        dfs(i, componenta);
      }
    }
    int nr = 0;
    for (int i = 1; i <= n; ++i)  {
      if (a[i] == 0)
        continue;
      if (!ok[i])
        dijkstra(i, ++nr);
    }
  }

}

int main()  {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	initial::solve();
	select_points::select_points();
	int q, x, y;
	cin >> q;
	while (q--)  {
		cin >> x >> y;
		if (comp[x] != comp[y] || comp[x] == 0 || comp[y] == 0)  {
			cout << 0 << '\n';
			continue;
		}
//    cout << x << ' ' << y << '\n';
		int ans = 0;
		for (auto it = dist[x].begin(); it != dist[x].end(); ++it)  {
//      cout << it -> first << ' ' << it -> second << ' ' << dist[y][it -> first] << '\n';
			if (dist[y][it -> first])
				ans = max(ans, min(it -> second, dist[y][it -> first]));
      else dist[y].erase(it -> first);
		}
		cout << ans << '\n';
	}
	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 13
• Subtask 3: 12 / 12
• Subtask 4: 19 / 19
• Subtask 5: 0 / 46