Submission #833467

#	Time	Username	Problem	Language	Result	Execution time	Memory
833467		vjudge1	Commuter Pass (JOI18_commuter_pass)	C++17	15 / 100	349 ms	23104 KiB

commuter_pass

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

#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
typedef long long ll;
const ll MAXN = 1e5 + 5;
const ll INF = 4e18;
#define endl '\n'
#define pll pair <ll, ll>
#define fi first
#define se second

ll n, m, s, t, u, v;
vector < vector <pll> > adj;
ll dis [MAXN];
ll vis [MAXN];
priority_queue <pll, vector <pll>, greater <pll> > pq;
ll pred [MAXN];

ll dijkstra(ll x, ll y){
    for(ll i = 1; i <= n; i++){
        vis[i] = false;
        dis[i] = INF;
    }
    vis[x] = true;
    dis[x] = 0;
    pq.push({dis[x], x});
    while(!pq.empty()){
        ll discur = pq.top().fi, cur = pq.top().se;
        pq.pop();
        if(!vis[cur]) vis[cur] = true;
        for(auto nex : adj[cur]){
            if(!vis[nex.se] && discur + nex.fi < dis[nex.se]){
                pred[nex.se] = cur;
                dis[nex.se] = discur + nex.fi;
                pq.push({dis[nex.se], nex.se});
            }
        }
    }
    return dis[y];
}

int main(){
    cin >> n >> m >> s >> t >> u >> v;
    adj.resize(n+1);
    for(ll i = 1; i <= m; i++){
        ll x, y, z; cin >> x >> y >> z;
        adj[x].push_back({z, y});
        adj[y].push_back({z, x});
    }
    ll z = dijkstra(s, t);
    // for(ll i = 1; i <= n; i++){
    //     cout << dis[i] << endl;
    // }
    // cout << z << endl;
    ll tmp = t;
    while(pred[tmp] != 0){
        adj[tmp].push_back({0, pred[tmp]});
        adj[pred[tmp]].push_back({0, tmp});
        tmp = pred[tmp];
    }
    cout << dijkstra(u, v) << endl;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:52:8: warning: unused variable 'z' [-Wunused-variable]
   52 |     ll z = dijkstra(s, t);
      |        ^

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