Submission #769353

#TimeUsernameProblemLanguageResultExecution timeMemory
769353AloraCommuter Pass (JOI18_commuter_pass)C++17
0 / 100
113 ms27348 KiB
#include <bits/stdc++.h> #define name "cownav" #define fi(i,a,b) for(int i = a; i <= b; i++) #define fid(i,a,b) for(int i = a; i >= b; i--) #define ll long long #define f first #define se second #define pii pair<ll, int> #define getbit(i, j) ((i >> j) & 1) #define pb push_back #define all(v) v.begin(), v.end() #define maxn 100005 const int M = 1e9 + 7; using namespace std; int n, m, S, T, U, V, xd[maxn]; struct dl{int f, se, id;}; vector <dl> g[maxn]; ll L[maxn]; void dij(){ fi(i, 1, n) L[i] = 1e18; L[S] = 0; priority_queue <pii> q; q.push({0, S}); while(q.size()){ ll h = -q.top().f; int u = q.top().se; q.pop(); if(h != L[u]) continue; for(auto e: g[u]){ int v = e.f, w = e.se; if(L[v] > L[u] + w){ L[v] = L[u] + w; q.push({-L[v], v}); } } } } void dfs(int u){ for(auto e: g[u]){ int v = e.f, w = e.se, id = e.id; if(xd[id]) continue; xd[id] = 1; if(L[v] + w == L[u]) xd[id] = 2; dfs(v); } } void dij1(){ fi(i, 1, n) L[i] = 1e18; L[S] = 0; priority_queue <pii> q; q.push({0, S}); while(q.size()){ ll h = -q.top().f; int u = q.top().se; q.pop(); if(h != L[u]) continue; for(auto e: g[u]){ int v = e.f, w = e.se, id = e.id; if(xd[id] == 2) w = 0; if(L[v] > L[u] + w){ L[v] = L[u] + w; q.push({-L[v], v}); } } } } signed main(){ ios_base::sync_with_stdio(0); cin.tie(NULL); // freopen(name".in", "r", stdin); //freopen(name".out", "w", stdout); cin >> n >> m; cin >> S >> T >> U >> V; fi(i, 1, m){ int u, v, z; cin >> u >> v >> z; g[u].pb({v, z, i}); g[v].pb({u, z, i}); } dij(); dfs(T); // fi(i, 1, m) cout << xd[i] << " "; cout << endl; dij1(); cout << L[V]; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...