Submission #1009237

#TimeUsernameProblemLanguageResultExecution timeMemory
1009237christinelynnCommuter Pass (JOI18_commuter_pass)C++17
15 / 100
1882 ms66740 KiB
#include <bits/stdc++.h> using namespace std; # define int long long # define fir first # define sec second # define pb push_back # define endl "\n" const int cnst = 2e5+5; bool mutipletestcase = 0; //bool debug = false; void solve() { // cerr << "IN" << endl; int n, m; cin >> n >> m; int s, t; cin >> s >> t; int u, v; cin >> u >> v; vector<pair<int, int>> vec[cnst]; tuple<int, int, int> edge[m+5]; map<pair<int, int>, int> mp; int par[n+5]; for(int i = 1; i<=m; i++) { int a, b, c; cin >> a >> b >> c; // cerr << a << " " << b << " " << c << endl; vec[a].pb({b, c}); vec[b].pb({a, c}); mp[{a, b}] = i; mp[{b, a}] = i; edge[i] = {a, b, c}; } priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq; pq.push({0, s, 0}); bool vis[n+5]; bool check[m+5]; memset(vis, 0, sizeof(vis)); memset(check, 0, sizeof(check)); par[s] = 0; while(!pq.empty()) { auto[ene, idx, pr] = pq.top(); pq.pop(); cerr << ene << " " << idx << " " << pr << endl; if(idx == t) { int now = t; par[now] = pr; while(par[now] != 0) { check[mp[{now, par[now]}]] = 1; now = par[now]; } } if(vis[idx]) continue; vis[idx] = 1; par[idx] = pr; for(auto[v, wei]: vec[idx]) if(!vis[v]) { pq.push({ene+wei, v, idx}); } } vector<pair<int, int>> vec2[n+5]; for(int i = 1; i<=m; i++) if(!check[i]) { auto[a, b, c] = edge[i]; vec2[a].pb({b, c}); vec2[b].pb({a, c}); } else { auto[a, b, c] = edge[i]; vec2[a].pb({b, 0}); vec2[b].pb({a, 0}); } memset(vis, 0, sizeof(vis)); pq.push({0, u, 0}); while(!pq.empty()) { auto[ene, idx, pr] = pq.top(); pq.pop(); if(idx == v) { cout << ene << endl; return; } if(vis[idx]) continue; vis[idx] = 1; par[s] = pr; for(auto[v, wei]: vec2[idx]) if(!vis[v]) { pq.push({ene+wei, v, idx}); } } } signed main() { ios_base::sync_with_stdio(false); cin.tie(0); int t = 1; if(mutipletestcase) 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...