#include <iostream>
#include <stack>
#include <queue>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <climits>
#include <cmath>
#include <unordered_map>
#include <unordered_set>
#include <numeric>
#include <iomanip>
#include <cstring>
#include <stdio.h>
#include <assert.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<long long> vll;
typedef pair<ll,ll> pll;
#define double long double
#define F first
#define S second
const double eps = 1e-9;
#define FOR(i,a,b) for(long long i=a;i<b;i++)
#define all(v) v.begin(),v.end()
template <typename I>
void print(vector<I> &v){
FOR(i,0,v.size()){cout << v[i] << " ";}
cout << "\n";
}
ll gcd(ll a,ll b){
if(a==0){return b;}
else if(b==0){return a;}
else if(a<b){return gcd(b%a,a);}
else{return gcd(a%b,b);}
}
ll lcm(ll a,ll b){
return (a/gcd(a,b))*b;
}
void setIO(string name = "") {
freopen((name + ".in").c_str(), "r", stdin); // see /general/input-output
freopen((name + ".out").c_str(), "w", stdout);
}
void init_code(){
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
}
ll MAXN = 1e17;
ll func(vector<vector<pll>> &adj1,vector<vector<pll>> &adj,ll n,ll u,ll v){
FOR(i,0,n){
for(pll p:adj1[i]){
adj[i].push_back(p);
}
}
vll dist(n,MAXN);
vector<bool> visited(n,false);
priority_queue<pll,vector<pll>,greater<pll>> pq;
pq.push({0,u});
dist[u] = 0;
while(!pq.empty()){
pll c = pq.top();
pq.pop();
if(visited[c.S]) continue;
visited[c.S] = true;
for(pll &p:adj[c.S]){
ll alt = c.F+p.S;
if(alt<dist[p.F]){
dist[p.F] = alt;
pq.push({alt,p.F});
}
}
}
return dist[v];
}
void solve(){
// store very big numbers may mean log2
ll n,m;
cin >> n >> m;
n++;
ll s,t;
cin >> s >> t;
ll u,v;
cin >> u >> v;
vector<vector<pll>> adj(n);
FOR(i,0,m){
ll a,b,c;
cin >> a >> b >> c;
adj[a].push_back({b,c});
adj[b].push_back({a,c});
}
vll dist(n,MAXN);
vector<vll> prev(n);
vector<bool> visited(n,false);
priority_queue<pll,vector<pll>,greater<pll>> pq;
pq.push({0,s});
dist[s] = 0;
while(!pq.empty()){
pll c = pq.top();
pq.pop();
if(visited[c.S]) continue;
visited[c.S] = true;
for(pll &p:adj[c.S]){
ll alt = c.F+p.S;
if(alt<dist[p.F]){
dist[p.F] = alt;
prev[p.F].clear();
prev[p.F].push_back(c.S);
pq.push({alt,p.F});
}
else if(alt==dist[p.F]){
prev[p.F].push_back(c.S);
}
}
}
dist.clear();
vector<vector<pll>> adj1(n);
queue<ll> q;
q.push(t);
while(!q.empty()){
ll c = q.front();
q.pop();
for(ll i:prev[c]){
adj1[c].push_back({i,0});
q.push(i);
}
}
prev.clear();
vector<vector<pll>> adj2(n);
FOR(i,0,n){
for(pll j:adj1[i]){
adj2[j.F].push_back({i,0});
}
}
cout << min(func(adj,adj1,n,u,v),func(adj,adj2,n,u,v)) << "\n";
}
signed main(){
//setIO
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// init_code();
ll t=1;
// cin >> t;
while(t--){
solve();
}
return 0;
}
Compilation message (stderr)
commuter_pass.cpp: In function 'void setIO(std::string)':
commuter_pass.cpp:45:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
45 | freopen((name + ".in").c_str(), "r", stdin); // see /general/input-output
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:46:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
46 | freopen((name + ".out").c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp: In function 'void init_code()':
commuter_pass.cpp:50:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
50 | freopen("input.txt","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:51:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
51 | freopen("output.txt","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |