Submission #1273750

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273750		quanw267	Commuter Pass (JOI18_commuter_pass)	C++17	0 / 100	74 ms	13172 KiB

commuter_pass

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pii pair<long long,long long>
#define fast ios_base::sync_with_stdio(0), cin.tie(0);

using namespace std;
const long long N = 1e5;
const long long INF = 1e16;

vector<pii> g[N+5];

void path(long long n, long long u, long long *d){
    vector<long long> vis(n+2, 0);
    for(long long i=1; i<=n; i++) d[i] = INF;

    d[u] = 0;
    priority_queue<pii,vector<pii>,greater<pii>> q;
    q.push({0,u});
    while(!q.empty()){
        auto [kc,u] = q.top();
        q.pop();
        if(vis[u]) continue;
        vis[u] = 1;
        for(auto [v,w]:g[u]){
            if(d[v] > d[u] + w){
                d[v] = d[u] + w;
                q.push({d[v],v});
            }
        }
    }
}

long long d[1005][1005];   // an toàn hơn là 1005 thay vì 1000

int main(){
    fast
    long long n,m;
    cin >> n >> m;
    long long A,B; cin >> A >> B;
    long long C,D; cin >> C >> D;
    for(long long i=1; i<=m; i++){
        long long u,v,w;
        cin >> u >> v >> w;
        g[u].push_back({v,w});
        g[v].push_back({u,w});
    }
    if(n <= 1000){
        for(long long i=1; i<=n; i++)
            path(n, i, d[i]);

        ll res = d[C][D];
        ll kcAB = d[A][B];

        for(int u=1; u<=n; u++){
            for(auto [v,w]: g[u]){

                if(u < v){
                    if(d[A][u] + w + d[v][B] == kcAB){
                        res = min(res, d[C][u] + d[v][D]);
                        res = min(res, d[C][v] + d[u][D]);
                    }
                }
            }
        }

        cout << res;
        return 0;
    }
    return 0;
}

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