Submission #1223826

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223826		Bui_Quoc_Cuong	Commuter Pass (JOI18_commuter_pass)	C++20	15 / 100	2095 ms	24608 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std ; 
#define int long long

typedef long long ll ;
typedef pair<int, int> ii ;
typedef vector<int> vi ;
typedef vector<ii> vii ; 

#define fi first
#define se second
#define pb push_back
#define endl '\n'
#define all(a) a.begin(),a.end()

#define FOR(i,a,b) for(int i(a) ; i <= (int)(b) ; i++)
#define FORD(i,a,b) for(int i(a) ; i >= (int)(b) ; i--)
#define FORN(i,a,b) for(int i(a) ; i < (int)b ; i++)
#define sz(a) (int)a.size()
#define MASK(a) (1ll << (i))
#define BIT(mask,i) ((mask>>i)&1)

template<class X, class Y> bool maxi(X &x, const Y &y) {return (x < y ? x = y, 1 : 0) ;}
template<class X, class Y> bool mini(X &x, const Y &y) {return (x > y ? x = y, 1 : 0) ;}

const int MAXN = 1e5 + 5 ;
const int mod = 1e9 + 7 ; 
const ll inf = 1e18 ; 
const int oo = 2e9 ; 

int n , m , S , T , U , V ; 
vii g[MAXN] ;
int dist[MAXN][4] ;
int best[MAXN][4] ; 
int ans ;

void init() {
    cin >> n >> m ;
    cin >> S >> T ; 
    cin >> U >> V ;
    FOR(i,1,m) {
        int u , v , w ; cin >> u >> v >> w ; 
        g[u].pb(ii(v,w)) ; g[v].pb(ii(u,w)) ; 
    } 
}

void dijkstra(int st,int type) {
    FOR(i,1,n) dist[i][type] = inf ; 
    dist[st][type] = 0 ; 
    priority_queue<ii,vector<ii>,greater<ii>> pq ; 
    pq.push({0 , st}) ; 
    while(!pq.empty()) {
        int u = pq.top().se ; 
        int c = pq.top().fi ; 
        pq.pop() ; 
        if(c > dist[u][type]) continue ; 
        for(auto [v,w] : g[u]) {
            if(mini(dist[v][type],c+w)) {
                pq.push({c + w , v}) ; 
            }
        }
    }
}

void dfs(int u) {
    best[u][0] = dist[u][1] ; 
    best[u][1] = dist[u][2] ; 
    for(auto [v,w] : g[u]) {
        if( (dist[v][0] + w) != dist[u][0]) continue ; 
        dfs(v) ; 
        mini(best[u][0],best[v][0]) ; 
        mini(best[u][1],best[v][1]) ; 
    }
    mini(ans,best[u][0] + dist[u][2]) ; 
    mini(ans,best[u][1] + dist[u][1]) ; 
}

void solve() {
    dijkstra(S,0) ; 
    dijkstra(U,1) ; 
    dijkstra(V,2) ; 
    ans = dist[V][1] ; 
    dfs(T) ;
    cout << ans ;
}

signed main() {
    #define task "bus"
    ios_base::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0) ; 
    if(fopen(task".inp","r")) {
        freopen(task".inp","r",stdin) ; freopen(task".out","w",stdout) ; 
    }
    init() ; solve() ;
    cerr << "TIME : " << clock() * 0.001 << "s" << endl ;
    return 0 ; 
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:91:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |         freopen(task".inp","r",stdin) ; freopen(task".out","w",stdout) ;
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:91:48: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |         freopen(task".inp","r",stdin) ; freopen(task".out","w",stdout) ;
      |                                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 16
• Subtask 2: 15 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 45