Submission #666923

#TimeUsernameProblemLanguageResultExecution timeMemory
666923Markomafko972Commuter Pass (JOI18_commuter_pass)C++14
31 / 100
770 ms30048 KiB
#include <bits/stdc++.h> #define X first #define Y second #define pb push_back #define pii pair<int, int> typedef long long ll; using namespace std; const int MOD = 1e9 + 7; const ll INF = 1e18; const int OFF = (1 << 20); int n, m, a, b, c; int poc1, kr1, poc2, kr2; vector< pair<int, int> > v[100005]; set< pair<ll, int> > s; ll dist[100005]; vector<int> gdje[100005]; int bio[100005]; void dijkstra() { while (!s.empty()) { ll cost = s.begin() -> first; int cvor = s.begin() -> second; s.erase(s.begin()); for (int i = 0; i < v[cvor].size(); i++) { int sus = v[cvor][i].X; int d = v[cvor][i].Y; if (cost+d < dist[sus]) { s.erase({dist[sus], sus}); dist[sus] = cost+d; s.insert({dist[sus], sus}); gdje[sus].clear(); gdje[sus].push_back(cvor); } else if (cost+d == dist[sus]) { gdje[sus].push_back(cvor); } } } } void dfs(int x) { if (bio[x] == 1) return; bio[x] = 1; for (int i = 0; i < gdje[x].size(); i++) { v[gdje[x][i]].push_back({x, 0}); dfs(gdje[x][i]); } } int main () { ios_base::sync_with_stdio(false); cin.tie(0); cin >> n >> m; cin >> poc1 >> kr1; cin >> poc2 >> kr2; for (int i = 0; i < m; i++) { cin >> a >> b >> c; v[a].push_back({b, c}); v[b].push_back({a, c}); } for (int i = 1; i <= n; i++) { if (i != poc1) dist[i] = INF; s.insert({dist[i], i}); } dijkstra(); dfs(kr1); for (int i = 1; i <= n; i++) { if (i != poc2) dist[i] = INF; else dist[i] = 0; s.insert({dist[i], i}); } dijkstra(); ll sol = dist[kr2]; for (int i = 1; i <= n; i++) { if (i != kr2) dist[i] = INF; else dist[i] = 0; s.insert({dist[i], i}); } dijkstra(); sol = min(sol, dist[poc2]); cout << sol; return 0; }

Compilation message (stderr)

commuter_pass.cpp: In function 'void dijkstra()':
commuter_pass.cpp:28: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]
   28 |   for (int i = 0; i < v[cvor].size(); i++) {
      |                   ~~^~~~~~~~~~~~~~~~
commuter_pass.cpp: In function 'void dfs(int)':
commuter_pass.cpp:51:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |  for (int i = 0; i < gdje[x].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...