Submission #1264126

#TimeUsernameProblemLanguageResultExecution timeMemory
1264126bnd2100Commuter Pass (JOI18_commuter_pass)C++20
0 / 100
203 ms30368 KiB
/* * @Author: Twynzz * @Last Modified by: Twynzz * @Note For This Problem: https://wbd.ms/share/v2/aHR0cHM6Ly93aGl0ZWJvYXJkLm1pY3Jvc29mdC5jb20vYXBpL3YxLjAvd2hpdGVib2FyZHMvcmVkZWVtL2NmODRmYTFjYTY2NjRiNmViYjc1MzU1OTNjYmZjYzZhX0JCQTcxNzYyLTEyRTAtNDJFMS1CMzI0LTVCMTMxRjQyNEUzRF9iMDY2ZDUzNC1iMDIzLTQ1ZDQtOGNiNS03MDEwOWE0NjcwNTg= */ #include <bits/stdc++.h> using namespace std; // ------------ Define ------------ #define el "\n" #define int long long #define ld long double #define str string #define file(name) {freopen(name".inp","r",stdin);freopen(name".out","w",stdout);} #define IOS {std::ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);} #define _TBN_ signed main() #define setp(n) setprecision(n)<< fixed #define fi first #define se second #define ii pair<int,int> #define gcd(a,b) __gcd(a,b) #define tup pair<int,ii> #define pb push_back #define pf push_front #define eb emplace_back #define sz(v) (int)v.size() const int maxn = 3e5+9; const long long oo = 1e18; const int MOD = 1e9+7, Mod = 998244353; const int base = 311; template<class X> bool maximize(X &a, const X &b) { if (a<b) { a = b; return 1; } return 0; } template<class X> bool minimize(X &a, const X &b) { if (a>b) { a = b; return 1; } return 0; } namespace sub1 { bool checkSub1(); void sub1(); } namespace sub2 { bool checkSub2(); void sub2(); } namespace sub3 { bool checkSub3(); void sub3(); } int lcm(int a, int b) { return a/gcd(a,b)*b; } int sqr(int x) {return x*x;} inline bool MASK(int mask, int bit) {return ((mask>>bit)&1);} inline long long F(int n) {return n*(n+1)/2;} inline int add(int a, int b, int m = MOD) {return ((a%m+b%m)%m+m)%m;} inline int sub(int a, int b, int m = MOD) {return ((a-b)%m+m)%m;} inline int mul(int a, int b, int m = MOD) {return ((a%m)*(b%m))%m;} int dx[] = {1, 0}; int dy[] = {0, 1}; // ------------ Code ------------ int n, m, S, T, U, V; vector<ii> adj[maxn]; _TBN_ { IOS; if (fopen("BOOKR.inp","r")) file("BOOKR"); cin >>n >>m >>S >>T >>U >>V; for(int i = 1; i <= m; i++) { int u, v, c; cin >>u >>v >>c; adj[u].eb(v, c); adj[v].eb(u, c); } for(int i = 1; i <= 1; i++) { if (sub1::checkSub1()) {sub1::sub1(); continue;} // if (sub2::checkSub2()) {sub2::sub2(); continue;} // if (sub3::checkSub3()) {sub3::sub3(); continue;} } return 0; } namespace sub1 { bool checkSub1() { return 1; } int dis[3][maxn]; bool vis[maxn]; void dijk(int s, int id) { fill(dis[id] + 1, dis[id] + 1 + n, oo); fill(vis + 1, vis + 1 + n, 0); dis[id][s] = 0; priority_queue<ii, vector<ii>, greater<ii>> q; q.emplace(0, s); while(!q.empty()) { int u = q.top().se; q.pop(); if (vis[u]) continue; vis[u] = 1; for(ii cur : adj[u]) { int v = cur.fi, w = cur.se; if (minimize(dis[id][v], dis[id][u] + w)) q.emplace(dis[id][v], v); } } } vector<int> e[maxn]; int dp[maxn][4], ans; void dfs(int u) { dp[u][1] = dis[1][u]; // U -> V xuoi theo dijk dp[u][2] = dis[2][u]; // V -> U xuoi theo dijk if (u == T) return; for(int v : e[u]) { dfs(v); minimize(dp[u][1], dp[v][1]); minimize(dp[u][2], dp[v][2]); } minimize(ans, dp[u][1] + dis[2][u]); minimize(ans, dis[1][u] + dp[u][2]); // cout<< u<< ' '<< dp[u][1]<< ' '<< dis[2][u]<< ' '<< ans<< el; // cout<< u<< ' '<< dis[1][u]<< ' '<< dp[u][2]<< el; } void sub1() { dijk(S, 0); dijk(U, 1); dijk(V, 2); dijk(T, 3); for(int u = 1; u <= n; u++) { for(ii cur : adj[u]) { int v = cur.fi, w = cur.se; if (dis[0][u] + w + dis[3][v] == dis[0][T]) { e[u].eb(v); // cout<< u<< ' '<< v<< ' '<< w<< el; } } } ans = oo; dfs(S); cout<< ans<< el; } }

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:17:28: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 | #define file(name) {freopen(name".inp","r",stdin);freopen(name".out","w",stdout);}
      |                     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:98:33: note: in expansion of macro 'file'
   98 |     if (fopen("BOOKR.inp","r")) file("BOOKR");
      |                                 ^~~~
commuter_pass.cpp:17:58: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 | #define file(name) {freopen(name".inp","r",stdin);freopen(name".out","w",stdout);}
      |                                                   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:98:33: note: in expansion of macro 'file'
   98 |     if (fopen("BOOKR.inp","r")) file("BOOKR");
      |                                 ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...