| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 851854 | themaver1cks | Commuter Pass (JOI18_commuter_pass) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/**
｡∠(*・ω･)っ ⌒ 由 ~ (( ,,・з・,, ))
_Π_____。
/______/~＼
｜ 田田｜門｜
**/
#include <bits/stdc++.h>
using namespace std;
#define fori(i, l, r) for(int (i) = (l); i < (r); ++i)
#define forie(i, l, r) for (int (i) = (l); i <= (r); ++i)
#define ford(i, l, r) for (int (i) = (l); i > (r); --i)
#define forde(i, l, r) for (int (i) = (l); i >= (r); --i)
//#define int long long
//#define i_inf INT_MAX
#define inf LLONG_MAX
#define ii pair<int,int>
#define fi first
#define se second
#define gcd __gcd
#define lcm(x,y) x * y/ gcd(x,y)
#define pb push_back
#define sz size
#define all(x) begin(x), end(x)
#define fastio ios_base::sync_with_stdio(0); cin.tie(nullptr);
#define el "\n"
#define sp " "
//
int dr[] = {-1, 0, 1, 0};
int dc[] = {0, 1, 0, -1};
// var declare
const int maxn = 1e5 + 3;
const int i_inf = 1e9;
int n, m, s, t, x, y;
// ds declare
vector <ii> adj[maxn];
vector<vector<int>> path;
vector <int> p[maxn];
//
void dijkstra()
{
priority_queue <ii, vector<ii>, greater<ii>> pq;
pq.push({0, s});
vector <int> d(n+3, i_inf);
d[s] = 0;
while (pq.sz())
{
int e = pq.top().fi;
int u = pq.top().se;
pq.pop();
if (e != d[u]) continue;
for (ii edge: adj[u])
{
int v = edge.fi, w = edge.se;
if (d[v] > d[u] + w)
{
p[v].clear();
p[v].pb(u);
d[v] = d[u] + w;
pq.push({d[v], v});
}
else if (d[v] == d[u] + w) p[v].pb(u);
}
}
}
//
void dewey(vector<int>& trace, int node)
{
if (node == s)
{
path.pb(trace);
return;
}
for (int v: p[node])
{
trace.pb(v);
dewey(trace, v);
trace.pop_back();
}
}
//
void solve()
{
cin >> n >> m >> s >> t >> x >> y;
forie(i, 1, m)
{
int u, v, w; cin >> u >> v >> w;
adj[u].pb({v, w});
adj[v].pb({u, w});
}
dijkstra();
vector <int> trace;
trace.pb(t);
for (int v: p[t])
{
trace.pb(v);
dewey(trace, v);
trace.pop_back();
}
int ans = i_inf;
for (vector<int>& a: path)
{
reverse(a.begin(), a.end());
fori(i, 1, a.sz())
{
int u = a[i-1], v = a[i];
adj[u].pb({v, 0});
adj[v].pb({u, 0});
}
priority_queue <ii, vector<ii>, greater<ii>> pq;
vector <int> dis(n+3, i_inf);
dis[x] = 0;
pq.push({0, x});
while (pq.sz())
{
int e = pq.top().fi;
int u = pq.top().se;
pq.pop();
if (e != dis[u]) continue;
for (int i = adj[u].sz()-1; i >= 0; --i)
{
int v = adj[u][j].fi, w = adj[u][j].se;
if (dis[v] > dis[u] + w)
{
dis[v] = dis[u] + w;
pq.push({dis[v], v});
}
}
}
ans = min(ans, dis[y]);
fori(i, 1, a.sz())
{
adj[a[i-1]].pop_back();
adj[a[i]].pop_back();
}
}
cout << ans;
}
//
void multi_test()
{
int t;
cin >> t;
while (t--) solve();
}
//
int32_t main()
{
fastio;
solve();
return 0;
}
/**
5 7
1 3
4 5
1 2 10
1 3 30
1 4 15
2 3 10
4 3 5
3 5 10
4 5 12
**/