제출 #1101908

#제출 시각아이디문제언어결과실행 시간메모리
1101908KasymKCommuter Pass (JOI18_commuter_pass)C++17
0 / 100
267 ms48372 KiB
#include "bits/stdc++.h" using namespace std; #define ff first #define ss second #define all(v) v.begin(), v.end() #define ll long long #define pb push_back #define pii pair<int, int> #define pli pair<ll, int> #define pll pair<ll, ll> #define tr(i, c) for(auto i = c.begin(); i != c.end(); ++i) #define wr puts("----------------") template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;} template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;} const int N = 2e5+5; const ll INF = 1e18; ll dis[N], diss[N]; int n; void dij(int s, vector<vector<pii>> &adjx){ for(int i = 1; i <= n; ++i) dis[i] = INF; priority_queue<pli, vector<pli>, greater<pli>> pq; pq.push({0, s}); dis[s] = 0; while(!pq.empty()){ int x = pq.top().ss; ll val = pq.top().ff; pq.pop(); if(dis[x] != val) continue; tr(it, adjx[x]){ int a = it->ff, w = it->ss; if(umin(dis[a], dis[x]+w)) pq.push({dis[a], a}); } } } int main(){ vector<vector<pii>> adj, adj2; int m, s, t, u, v; scanf("%d%d%d%d%d%d", &n, &m, &s, &t, &u, &v); adj.assign(n+1, {}); adj2.assign(n+1, {}); vector<tuple<int, int, int>> A; for(int i = 1; i <= m; ++i){ int a, b, c; scanf("%d%d%d", &a, &b, &c); adj[a].pb({b, c}); adj[b].pb({a, c}); A.pb({a, b, c}); } dij(s, adj); for(int i = 1; i <= n; ++i) diss[i] = dis[i]; dij(t, adj); for(auto &i : A){ int a, b, c; tie(a, b, c) = i; bool did = 0, done = 0; if(diss[a]+dis[b]+c == diss[t]) did = 1; if(dis[a]+diss[b]+c == diss[t]) done = 1; if(did and done){ adj2[a].pb({b, 0}); adj2[b].pb({a, 0}); } else if(!did and !done){ adj2[a].pb({b, c}); adj2[b].pb({a, c}); } else if(did and !done){ adj2[a].pb({b, 0}); adj2[b].pb({a, c}); } else{ assert(!did and done); adj2[a].pb({b, c}); adj2[b].pb({a, 0}); } } dij(u, adj2); ll ans0 = dis[v]; for(int i = 0; i <= n+1; ++i) adj2[i].clear(); dij(t, adj); for(auto &i : A){ int a, b, c; tie(a, b, c) = i; bool did = 0, done = 0; if(diss[a]+dis[b]+c == diss[t]) did = 1; if(dis[a]+diss[b]+c == diss[t]) done = 1; if(did and done){ adj2[b].pb({a, 0}); adj2[a].pb({b, 0}); } else if(!did and !done){ adj2[b].pb({a, c}); adj2[a].pb({b, c}); } else if(did and !done){ adj2[b].pb({a, 0}); adj2[a].pb({b, c}); } else{ assert(!did and done); adj2[b].pb({a, c}); adj2[a].pb({b, 0}); } } dij(u, adj2); printf("%lld\n", min(ans0, dis[v])); assert(false); return 0; }

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

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:43:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |     scanf("%d%d%d%d%d%d", &n, &m, &s, &t, &u, &v);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:49:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |         scanf("%d%d%d", &a, &b, &c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...