| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 636921 | chjiao | Commuter Pass (JOI18_commuter_pass) | C++17 | 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 ll long long
#define newl '\n'
const int mod = 1e9+7;
const ll MAX = 0x3f3f3f3f3f3f3f3f;
const int mn = 1e5+1;
vector<vector<pair<ll,ll>>> neighbors(mn);
vector<ll> du(mn,LLONG_MAX/2);
vector<ll> dv(mn,LLONG_MAX/2);
vector<ll> ds(mn,LLONG_MAX/2);
vector<ll> dpu(mn,LLONG_MAX/2);
vector<ll> dpv(mn,LLONG_MAX/2);
// ll du[mn],dv[mn], ds[mn], dpu[mn], dpv[mn];
bool vis[mn];
ll ans;
void dijkstra(ll s, vector<int>& d) { // Source and destination
fill(vis, vis + 100001, false); //初始化visited为false
priority_queue<pair<ll, ll>> pq;
pq.push({0, s});
while (!pq.empty()) {
ll c, node;
tie(c, node) = pq.top(); //c: 从 start 到 node 的cost
pq.pop();
if (!vis[node]) {
d[node] = -c; //距离
vis[node] = true;
for (auto& i : neighbors[node]) pq.push({c - i.second, i.first});
}
}
// fill(vis, vis + mn, false);
// using T = pair<ll,ll>; priority_queue<T,vector<T>,greater<T>> pq;
// d[s] = 0; // The shortest path from a node to itself is 0
// pq.push({0, s});
// while (!pq.empty()) {
// ll pos, cost;
// tie(pos, cost) = pq.top();
// pq.pop();
// if(vis[pos]==true){
// continue;
// }
// if(!vis[pos]) {
// vis[pos] = true;
// d[pos] = cost;
// for (auto & [place, value]: neighbors[pos]) {
// pq.push({cost+value, place});
// }
// }
// // for (auto & [place, value]: neighbors[pos]) {
// // // If we can reach a neighbouring node faster,
// // // we update its minimum distance
// // if (d[pos]+value < d[place]) {
// // d[place] = d[pos]+value;
// // pq.push({d[place], place});
// // }
// // }
// }
}
void dijkstra2(ll start, ll end) { // Source and destination
fill(vis,vis+mn , false);
fill(dpu.begin(),dpu.end(),LLONG_MAX/2);
fill(dpv.begin(), dpv.end(), LLONG_MAX/2);
// fill(dpu,dpu + mn,LLONG_MAX/2);
// fill(dpv, dpv+mn, LLONG_MAX/2);
priority_queue<pair<ll, pair<ll, ll>>> pq;
pq.push({0, {start, 0}}); //cost, curr node, pre node
dpu[0] = dpv[0] = LLONG_MAX/ 2;
while (!pq.empty()) {
ll c, node, par;
pair<ll, ll> p;
tie(c, p) = pq.top();
tie(node, par) = p;
pq.pop();
if (!vis[node]) {
vis[node] = true;
ds[node] = -c;
dpu[node] = min(du[node], dpu[par]);
dpv[node] = min(dv[node], dpv[par]);
for (auto i : neighbors[node]) pq.push({c - i.second, {i.first, node}}); //
} else if (-c == ds[node]) { //另外一条最短路近
if (min(du[node], dpu[par]) + min(dv[node], dpv[par]) <= dpu[node] + dpv[node]) {
dpu[node] = min(du[node], dpu[par]);
dpv[node] = min(dv[node], dpv[par]);
}
}
}
ans = min(ans, dpu[end] + dpv[end]);
// priority_queue<pair<ll,pair<ll, ll>>> pq;
// pq.push({0, {start,0}});
// dpu[0]= LLONG_MAX/2;
// dpv[0] = LLONG_MAX/2;
// while (pq.size()) {
// ll cost, curr, last;
// cost = pq.top().first;
// curr = pq.top().second.first;
// last = pq.top().second.second;
// pq.pop();
// if(vis[curr]!=true){
// vis[curr] = true;
// ds[curr] = -cost;
// dpu[curr] = min(dpu[last], du[curr]);
// dpv[curr] = min(dpv[last], dv[curr]);
// for (auto [place, value] : neighbors[curr]) {
// // If we can reach a neighbouring node faster,
// // we update its minimum distance
// if(ds[place]> ds[curr]+value){
// pq.push({-cost-value,{place, curr}});
// }
// }
// }else if (-cost == ds[curr] ) {
// if(min(dpu[last], du[curr]) + min(dpv[last], dv[curr]) < dpu[curr]+dpv[curr]){
// dpu[curr] = min(dpu[last], du[curr]);
// dpv[curr] = min(dpv[last], dv[curr]);
// }
// }
// }
// ans = min(ans, dpu[end]+dpv[end]);
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(0);
// freopen("CommuterPass.in", "r", stdin);
//freopen("nocross.out", "w", stdout);
ll N,M,S,T,U,V,a,b,c;
cin >> N >> M;
cin >> S >> T >> U >> V;//s,t is free, U,V needs minimizing
// S--;T--;U--;V--;
for(int i=0; i<M; i++){
cin >> a >> b >> c;
// a--;
// b--;
neighbors[a].push_back(make_pair(b,c));
neighbors[b].push_back(make_pair(a,c));
}
dijkstra(U, du);
dijkstra(V, dv);
ans = du[V];
dijkstra2(S,T);
dijkstra2(T,S);
cout << ans << endl;
}