Submission #1212218

#TimeUsernameProblemLanguageResultExecution timeMemory
1212218_noobCommuter Pass (JOI18_commuter_pass)C++20
0 / 100
2 ms2628 KiB
#pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops,02,no-stack-protector") #include <iostream> #include <string> #include <cstdio> #include <cstdlib> #include <cstring> #include <vector> #include <set> #include <map> #include <deque> #include <stack> #include <queue> #include <algorithm> #include <cassert> #include <random> #include <chrono> #include <iomanip> #include <cmath> #include <bitset> #include <functional> #include <numeric> #define int long long #define double long double #define ii pair<int,int> #define iii pair<int, ii > #define fi first #define se second #define getbit(x,y) (((x)>>(y))&1ll) #define turnon(x,y) ((x)|(1ll<<y)) #define turnof(x,y) ((x)^(1ll<<y)) #define oo 1e18 #define pb push_back #define all(x) x.begin(),x.end() #define con(mask) mask=(mask-1)&mask #define Unique(val) val.erase(unique(val.begin(),val.end()),val.end()) #define ll long long const int mod = 1e9 + 7; const int base = 11; using namespace std; int n, m, S, T, U, V; int dp_s[100005]; int dp_t[100005]; vector<ii> e[100005]; int dp[100005][3]; void solve() { cin >> n >> m >> S >> T >> U >> V; for(int i = 1; i <= n; i++) { dp_s[i] = oo; dp_t[i] = oo; } for(int i = 1; i <= m; i++) { int u, v, w; cin >> u >> v >> w; e[u].pb(make_pair(v, w)); e[v].pb(make_pair(u, w)); } priority_queue<ii, vector<ii>, greater<ii>> pq; dp_s[S] = 0; pq.push(make_pair(0, S)); while(!pq.empty()) { ii top = pq.top(); pq.pop(); int u = top.se; if(dp_s[u] < top.fi) continue; for(auto it : e[u]) { int v = it.fi, w = it.se; if(dp_s[v] > dp_s[u] + w) { dp_s[v] = dp_s[u] + w; pq.push(make_pair(dp_s[v], v)); } } } pq.push(make_pair(0, T)); dp_t[T] = 0; while(!pq.empty()) { ii top = pq.top(); pq.pop(); int u = top.se; if(dp_t[u] < top.fi) continue; for(auto it : e[u]) { int v = it.fi, w = it.se; if(dp_t[v] > dp_t[u] + w) { dp_t[v] = dp_t[u] + w; pq.push(make_pair(dp_t[v], v)); } } } priority_queue<pair<int, ii>, vector<pair<int, ii>>, greater<pair<int, ii>>> pq2; for(int i = 1; i <= n; i++) { dp[i][0] = oo; dp[i][1] = oo; dp[i][2] = oo; } dp[U][0] = 0; pq2.push(make_pair(0, make_pair(U, 0))); while(!pq2.empty()) { int u = pq2.top().se.fi; int t = pq2.top().se.se; int cost = pq2.top().fi; pq2.pop(); if(dp[u][t] < cost) continue; // 0 -> 1 phải đi qua 1 cạnh được cải tạo // 1 -> 1 vậy cạnh đó cũng phải được cải tạo luôn // 1 -> 2 nghĩa là hết cải tạo -> không cần đi qua cạnh // 2 -> 2 bình thường if(t == 0) { if(dp[u][1] > dp[u][0]) { dp[u][1] = dp[u][0]; pq2.push(make_pair(dp[u][1], make_pair(u, 1))); } for(auto it: e[u]) { int v = it.fi, w = it.se; if(dp[v][0] > dp[u][0] + w) { dp[v][0] = dp[u][0] + w; pq2.push(make_pair(dp[v][0], make_pair(v, 0))); } } } else if(t == 1) { if(dp[u][2] > dp[u][1]) { dp[u][2] = dp[u][1]; pq2.push(make_pair(dp[u][2], make_pair(u, 2))); } for(auto it: e[u]) { int v = it.fi, w = it.se; if((dp_s[u] + w + dp_t[v] == dp_s[T]) && dp[v][1] > dp[u][1]) { dp[v][1] = dp[u][1]; pq2.push(make_pair(dp[v][1], make_pair(v, 1))); } } } else if(t == 2) { for(auto it: e[u]) { int v = it.fi, w = it.se; if(dp[v][2] > dp[u][2] + w) { dp[v][2] = dp[u][2] + w; pq2.push(make_pair(dp[v][2], make_pair(v, 2))); } } } } int res = dp[V][0]; res = min(res, dp[V][1]); res = min(res, dp[V][2]); for(int i = 1; i <= n; i++) { dp[i][0] = oo; dp[i][1] = oo; dp[i][2] = oo; } dp[U][0] = 0; pq2.push(make_pair(0, make_pair(U, 0))); while(!pq2.empty()) { int u = pq2.top().se.fi; int t = pq2.top().se.se; int cost = pq2.top().fi; pq2.pop(); if(dp[u][t] < cost) continue; // 0 -> 1 phải đi qua 1 cạnh được cải tạo // 1 -> 1 vậy cạnh đó cũng phải được cải tạo luôn // 1 -> 2 nghĩa là hết cải tạo -> không cần đi qua cạnh // 2 -> 2 bình thường if(t == 0) { if(dp[u][1] > dp[u][0]) { dp[u][1] = dp[u][0]; pq2.push(make_pair(dp[u][1], make_pair(u, 1))); } for(auto it: e[u]) { int v = it.fi, w = it.se; if(dp[v][0] > dp[u][0] + w) { dp[v][0] = dp[u][0] + w; pq2.push(make_pair(dp[v][0], make_pair(v, 0))); } } } else if(t == 1) { if(dp[u][2] > dp[u][1]) { dp[u][2] = dp[u][1]; pq2.push(make_pair(dp[u][2], make_pair(u, 2))); } for(auto it: e[u]) { int v = it.fi, w = it.se; if((dp_t[u] + w + dp_s[v] == dp_t[S]) && dp[v][1] > dp[u][1]) { dp[v][1] = dp[u][1]; pq2.push(make_pair(dp[v][1], make_pair(v, 1))); } } } else if(t == 2) { for(auto it: e[u]) { int v = it.fi, w = it.se; if(dp[v][2] > dp[u][2] + w) { dp[v][2] = dp[u][2] + w; pq2.push(make_pair(dp[v][2], make_pair(v, 2))); } } } } res = min(res, dp[V][0]); res = min(res, dp[V][1]); res = min(res, dp[V][2]); cout << res; } signed main() { #ifndef ONLINE_JUDGE freopen("a.inp", "r", stdin); freopen("a.out", "w", stdout); #endif ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); int t = 1; //cin >> t; while(t--) { solve(); } } // ProTeam //(¯`·.·´¯) (¯`·.·´¯) //`·.¸(¯`·.·´¯)¸ .· //×°× ` ·.¸.·´ ×°×

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:234:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  234 |     freopen("a.inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:235:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  235 |     freopen("a.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...