Submission #1273748

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273748		quanw267	Commuter Pass (JOI18_commuter_pass)	C++17	0 / 100	82 ms	13176 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;

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] = 1e16;

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[1000][1000];

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]);

//cout << d[A][B];
for(long long x=1; x<=n; x++)
for(long long y=1; y<=n; y++){
   long long kc = d[A][B];
   if( d[A][x]+d[x][y]+d[y][B] == kc ) d[x][y] = d[y][x] = 0;
}
ll res = d[C][D];
for(long long x=1; x<=n; x++)
   for(long long y=1; y<=n; y++)
   if(d[x][y] == 0) res = min(res, d[C][x] + d[y][D]);

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

Compilation message (stderr)

commuter_pass.cpp:39:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   39 | main(){
      | ^~~~

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