Submission #561608

#	Time	Username	Problem	Language	Result	Execution time	Memory
561608		Aktan	Commuter Pass (JOI18_commuter_pass)	C++14	24 / 100	46 ms	1876 KiB

commuter_pass

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
template<class T>
using ordered_set = tree<T, null_type,less<T>, rb_tree_tag,tree_order_statistics_node_update>;
#define int long long
#define ft first
#define sc second
const int mod=1e9+7,INF=1e17,N=305;

int a[N][N];
main(){
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

	int n,m;
	cin >> n >> m;
	int s,t,u,v;
	cin >> s >> t >> u >> v;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(i!=j){
				a[i][j]=INF;	
			}
		}
	}
	for(int i=0;i<m;i++){
		int x,y,c;
		cin >> x >> y >> c;
		a[x][y]=min(a[x][y],c);
		a[y][x]=min(a[y][x],c);
	}
	
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			for(int k=1;k<=n;k++){
				a[j][k]=min(a[j][k],a[j][i]+a[i][k]);
			}
		}
	}
	int ans=a[u][v];
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(a[s][i]+a[i][j]+a[j][t]==a[s][t]){
				ans=min(ans,a[u][i]+a[j][v]);	
				ans=min(ans,a[u][j]+a[i][v]);	
			}
		}
	}
	cout << ans;
}

Compilation message (stderr)

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

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