제출 #1082875

#제출 시각아이디문제언어결과실행 시간메모리
1082875bundaunuoctuongCommuter Pass (JOI18_commuter_pass)C++14
15 / 100
2073 ms183424 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> using namespace std; using namespace __gnu_pbds; #define mod 1000000007 #define ull unsigned long long #define mll map<int,int> #define vll vector<int> #define pll pair<int, int> #define FOR(i, a, b) for(int i = a; i < b; i++) #define FOR1(i, a, b) for(int i = a; i <= b; i++) #define UNF(i, a, b) for(int i = b; i >= a; i--) #define UNF1(i, a, b) for(int i = b; i > a; i--) #define ll long long #define pb push_back #define mp make_pair #define X first #define Y second #define name "QUADQUERY" #define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); const int MAXN = 3e6 + 5; int n, m, s, t, x, y; vector<pll> g[MAXN]; ll d[MAXN], ans = LLONG_MAX; map<pll, bool> check; vector<int> edge[MAXN]; void Dijkstra(int p, int end) { fill(d, d + n + 1, LLONG_MAX); d[p] = 0; priority_queue<pll, vector<pll>, greater<pll>> q; q.push(mp(d[p], p)); while (!q.empty()) { int u = q.top().Y, cost = q.top().X; q.pop(); if (cost > d[u]) continue; if (u == end) break; for (const auto& x : g[u]) { if (d[x.X] > d[u] + x.Y) { d[x.X] = d[u] + x.Y; q.push(mp(d[x.X], x.X)); edge[x.X].clear(); } if (d[x.X] == d[u] + x.Y) edge[x.X].pb(u); } } } void Dijkstra2(int p, int end) { fill(d, d + n + 1, LLONG_MAX); d[p] = 0; priority_queue<pll, vector<pll>, greater<pll>> q; q.push(mp(d[p], p)); while (!q.empty()) { int u = q.top().Y, cost = q.top().X; q.pop(); if (cost > d[u]) continue; if (u == end) break; for (const auto& x : g[u]) { ll val = check[{u, x.X}] ? 0 : x.Y; if (d[x.X] > d[u] + val) { d[x.X] = d[u] + val; q.push(mp(d[x.X], x.X)); } } } } void DFS(int u, int end) { if (u == end) { Dijkstra2(x, y); ans = min(ans, d[y]); } for (const int& v : edge[u]) { check[{u, v}] = check[{v, u}] = true; DFS(v, end); check[{u, v}] = check[{v, u}] = false; } } void solve() { Dijkstra(s, t); DFS(t, s); cout << ans; } int main() { fast; if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); } cin >> n >> m >> s >> t >> x >> y; FOR1(i, 1, m) { int u, v, w; cin >> u >> v >> w; g[u].pb(mp(v, w)); g[v].pb(mp(u, w)); } solve(); return 0; }

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

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:92:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |         freopen(name".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:93:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |         freopen(name".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...