Submission #1291918

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291918		banmkh	Commuter Pass (JOI18_commuter_pass)	C++20	0 / 100	3 ms	3644 KiB

commuter_pass

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

#define ll long long
#define int long long
#define sz(a) ((int)a.size())
#define all(a) a.begin(), a.end()
#define arr2 array<int,2>
#define arr3 array<int,3>
#define arr4 array<int,4>
#define arr5 array<int,5>
#define el '\n'
#define pii pair<int,int>
#define __ <<' '<<
#define i128 __int128
#define IMPOSSIBLE return cout << "-1" << endl,void();
#define FILE "cowmbat"

const int N = 1e5 + 7;
const int MOD = 1e9 + 7;

vector<pii> e[N];

bool visited[N];

int res[4][N];

void dijstra(int start,int type){
    priority_queue<pii, vector<pii>, greater<>> q;
    q.push({0,start});
    res[type][start] = 0;

    while(sz(q)){
        auto [w,u] = q.top();q.pop();

        if(w > res[type][u])continue;

        for(auto [v,wv] : e[u]){
            if(res[type][v] <= w + wv)continue;
            res[type][v] = w + wv;
            q.push({w + wv, v});
        }
    }
}
int tmp[3][N];

void dijstraress(int start){
    priority_queue<arr2, vector<arr2>, greater<>> q;

    q.push({0,start});
    
    memset(tmp[1],60,sizeof tmp[1]);
    memset(tmp[2],60,sizeof tmp[2]);
    
    tmp[1][start] = res[1][start];
    tmp[2][start] = res[2][start];

    res[3][start] = tmp[1][start] + tmp[2][start];
    res[0][start] = 0;

    while(sz(q)){
        auto [w,u] = q.top();q.pop();

        if(w > res[0][u])continue;
        
        res[0][u] = 0;

        for(auto [v,wv] : e[u]){
            if(wv + w < res[0][v]){
                res[0][v] = wv + w;
                tmp[1][v] = min(tmp[1][u], res[1][v]);
                tmp[2][v] = min(tmp[2][u], res[2][v]);
                res[3][v] = min({res[3][u], res[2][v] + tmp[1][u], res[1][v] + tmp[2][u], res[2][v] + res[1][v]});
                q.push({wv + w,v});
            }
            else if(wv + w == res[0][v]){
                tmp[1][v] = min(tmp[1][v], res[1][v]);
                tmp[2][v] = min(tmp[2][v], res[2][v]);
                res[3][v] = min({res[3][u], res[2][v] + tmp[1][u], res[1][v] + tmp[2][u], res[2][v] + res[1][v]});
            }
        }
    }
}

void solve(){
    int n,m;
    cin >> n >> m;

    memset(res[0], 60, sizeof res[0]);
    memset(res[1], 60, sizeof res[2]);
    memset(res[2], 60, sizeof res[2]);
    memset(res[3], 60, sizeof res[3]);

    int S,T,U,V;
    cin >> S >> T >> U >> V;

    for(int i = 0;i < m; i++){
        int u,v,w;
        cin >> u >> v >> w;
        e[u].push_back({v,w});
        e[v].push_back({u,w});
    }

    dijstra(U,1);
    dijstra(V,2);
    dijstraress(S);

    cout << min(res[1][V],res[3][T]) << endl;
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

#ifdef LOCAL
    freopen("io\\ban.in","r",stdin);
    freopen("io\\ban.txt","w",stdout);
#elif !(ONLINE_JUDGE)
    freopen(FILE ".in","r",stdin);
    freopen(FILE ".out","w",stdout);
#endif

    int q(1);
    // cin >> q;
    while(q--) solve();
    return 0;
}

Compilation message (stderr)

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

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