Submission #681556

#TimeUsernameProblemLanguageResultExecution timeMemory
681556zeroesandonesCommuter Pass (JOI18_commuter_pass)C++17
15 / 100
360 ms27440 KiB
#include "bits/stdc++.h" using namespace std; typedef long long ll; typedef long double ld; typedef vector<ll> vi; typedef pair<ll, ll> pi; #define FOR(i, j, k) for (ll i = j; i < (ll) k; ++i) #define FORD(i, j, k) for (ll i = j; i >= (ll) k; --i) #define nl "\n" #define sp " " #define all(x) (x).begin(), (x).end() #define sc second #define fr first #define pb emplace_back struct edge { ll b, w; ll id; }; void solve() { ll n, m; cin >> n >> m; ll s, t; cin >> s >> t; ll u, v; cin >> u >> v; vector<edge> adj[n + 1]; FOR(i, 0, m) { ll a, b, c; cin >> a >> b >> c; edge curr; curr.b = b; curr.w = c; curr.id = i; adj[a].pb(curr); curr.b = a; adj[b].pb(curr); } pi from[n + 1] = {}; vi dist(n + 1, 1e15); bool vis[n + 1] = {}; priority_queue<pi> pq; pq.push({0, s}); dist[s] = 0; from[s] = {0, -1}; while(!pq.empty()) { ll x = pq.top().sc; pq.pop(); if(vis[x]) continue; vis[x] = true; for(auto [y, w, id] : adj[x]) { if(dist[y] > dist[x] + w) { dist[y] = dist[x] + w; pq.push({-dist[y], y}); from[y] = {x, id}; } } } ll curr = t; set<int> path; while(curr != s) { path.insert(from[curr].sc); curr = from[curr].fr; } memset(vis, 0, sizeof(vis)); dist = vi(n + 1, 1e15); dist[u] = 0; pq.push({0, u}); while(!pq.empty()) { int x = pq.top().sc; pq.pop(); if(vis[x]) continue; vis[x] = true; for(auto [y, w, id] : adj[x]) { if(path.count(id)) w = 0; if(dist[y] > dist[x] + w) { dist[y] = dist[x] + w; pq.emplace(-dist[y], y); } } } cout << dist[v] << nl; } signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); ll t = 1; // cin >> t; while (t--) { solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...