제출 #682745

#제출 시각아이디문제언어결과실행 시간메모리
682745Markomafko972Commuter Pass (JOI18_commuter_pass)C++14
100 / 100
679 ms35276 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, poc1, poc2, kr1, kr2, a, b, c; vector< pair<int, int> > v[100005]; ll dist[2][100005]; set< pair<ll, int> > s; ll udl[100005]; ll mini[100005]; int bio[100005]; pair< pair<ll, ll>, ll> rj[100005]; vector<int> e[100005]; void dijkstra(int w) { while (!s.empty()) { int cvor = s.begin() -> second; ll cost = s.begin() -> first; s.erase(s.begin()); for (int i = 0; i < v[cvor].size(); i++) { int sus = v[cvor][i].X; int cijena = v[cvor][i].Y; if (cost+cijena < dist[w][sus]) { s.erase({dist[w][sus], sus}); dist[w][sus] = cost+cijena; s.insert({dist[w][sus], sus}); } } } } void dijk() { while (!s.empty()) { int cvor = s.begin() -> second; ll cost = s.begin() -> first; s.erase(s.begin()); for (int i = 0; i < v[cvor].size(); i++) { int sus = v[cvor][i].X; int cijena = v[cvor][i].Y; if (cost+cijena < udl[sus]) { s.erase({udl[sus], sus}); udl[sus] = cost+cijena; s.insert({udl[sus], sus}); mini[sus] = min(mini[cvor], dist[1][sus]); e[sus].clear(); e[sus].push_back(cvor); } else if (cost+cijena == udl[sus]) { mini[sus] = min(mini[sus], mini[cvor]); e[sus].push_back(cvor); } } } } pair<pair<ll, ll>, ll> dfs(int x) { bio[x] = 1; ll minx = dist[0][x], miny = dist[1][x], minsve = INF; for (int i = 0; i < e[x].size(); i++) { if (bio[e[x][i]] == 0) { dfs(e[x][i]); } pair< pair<ll ,ll>, ll > tren = rj[e[x][i]]; minx = min(minx, tren.X.X); miny = min(miny, tren.X.Y); minsve = min(minsve, tren.Y); } rj[x] = {{minx, miny}, min({minx+dist[1][x], miny+dist[0][x], minsve})}; return rj[x]; } 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++) { dist[0][i] = INF; if (i == poc2) dist[0][i] = 0; s.insert({dist[0][i], i}); } dijkstra(0); for (int i = 1; i <= n; i++) { dist[1][i] = INF; if (i == kr2) dist[1][i] = 0; s.insert({dist[1][i], i}); } dijkstra(1); for (int i = 1; i <= n; i++) mini[i] = dist[1][i]; for (int i = 1; i <= n; i++) { udl[i] = INF; if (i == poc1) udl[i] = 0; s.insert({udl[i], i}); } dijk(); ll sold = dfs(kr1).Y; cout << min(sold, dist[0][kr2]); return 0; }

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

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