제출 #930329

#제출 시각아이디문제언어결과실행 시간메모리
930329lovrotCommuter Pass (JOI18_commuter_pass)C++17
16 / 100
430 ms18872 KiB
#include <algorithm> #include <set> #include <vector> #include <cstdio> #define X first #define Y second #define PB push_back using namespace std; typedef long long ll; typedef pair<int, int> pii; const int N = 1e5 + 10; const ll OO = 1e18; int n, m, s, t, p, k; vector<pii> G[N]; ll DP[N]; vector<int> DAG[N]; ll D[N]; auto comp = [](int a, int b) { return D[a] < D[b] || (D[a] == D[b] && a < b); }; set<int, decltype(comp)> S(comp); void dijkstra(int s, vector<ll> &V) { for(int i = 1; i <= n; ++i) D[i] = OO; D[s] = 0; S.insert(s); for(; !S.empty(); ) { int u = *S.begin(); S.erase(S.begin()); for(pii e : G[u]) if(D[e.X] > D[u] + e.Y) { S.erase(e.X); D[e.X] = D[u] + e.Y; S.insert(e.X); } } V.resize(N); for(int i = 1; i <= n; ++i) V[i] = D[i]; } vector<int> V; vector<ll> DS, DT, DK, DST; int main() { scanf("%d%d%d%d%d%d", &n, &m, &s, &t, &p, &k); for(int i = 0; i < m; ++i) { int u, v, w; scanf("%d%d%d", &u, &v, &w); G[u].PB({v, w}); G[v].PB({u, w}); } dijkstra(s, DS); dijkstra(t, DT); dijkstra(k, DK); for(int i = 1; i <= n; ++i) { V.PB(i); DP[i] = OO; } sort(V.begin(), V.end(), [](int a, int b) { return DS[a] > DS[b]; }); for(int u : V) { if(DS[u] + DT[u] == DS[t]) DP[u] = min(DP[u], DK[u]); for(pii e : G[u]) if(DS[u] + e.Y + DT[e.X] == DS[t]) { DP[u] = min(DP[u], DP[e.X]); // printf("%d -> %d\n", u, e.X); } } sort(V.begin(), V.end(), [](int a, int b) { return DT[a] > DT[b]; }); for(int u : V) { if(DS[u] + DT[u] == DS[t]) DP[u] = min(DP[u], DK[u]); for(pii e : G[u]) if(DT[u] + e.Y + DS[e.X] == DT[s]) { DP[u] = min(DP[u], DP[e.X]); // printf("%d -> %d\n", u, e.X); } } ll ans = OO; dijkstra(p, DST); // for(int u = 1; u <= n; ++u) printf("%d: s %lld t %lld u %lld v %lld dp %lld\n", u, DS[u], DT[u], DST[u], DK[u], DP[u]); for(int u = 1; u <= n; ++u) ans = min(ans, DST[u] + DP[u]); printf("%lld\n", ans); return 0; }

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

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:54:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |  scanf("%d%d%d%d%d%d", &n, &m, &s, &t, &p, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:57:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |   scanf("%d%d%d", &u, &v, &w);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...