Submission #860265

#	Time	Username	Problem	Language	Result	Execution time	Memory
860265		StefanSebez	Commuter Pass (JOI18_commuter_pass)	C++14	0 / 100	139 ms	262144 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define int long long
const int N=1e5+50;
const int inf=1e17;
vector<pair<int,int> >E[N];
signed main()
{
    int n,m;cin>>n>>m;
    int A,B;cin>>A>>B;
    int U,V;cin>>U>>V;
    int edges[n+1][n+1];
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) edges[i][j]=inf;
	int dp[n+1][n+1];
	for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) dp[i][j]=inf;
    for(int i=1;i<=m;i++)
	{
		int u,v,w;cin>>u>>v>>w;
		E[u].pb({v,w});
		E[v].pb({u,w});
		edges[u][v]=w;
		edges[v][u]=w;
		dp[u][v]=dp[v][u]=w;
	}
	for(int i=1;i<=n;i++) edges[i][i]=0;
	for(int i=1;i<=n;i++)
	{
		dp[i][i]=0;
		for(int j=1;j<=i;j++)
		{
			for(int k=1;k<i;k++)
			{
				dp[i][j]=min(dp[i][j],edges[i][k]+dp[k][j]);
			}
			dp[j][i]=dp[i][j];
		}
		for(int j=1;j<i;j++)
		{
			for(int k=1;k<i;k++)
			{
				dp[j][k]=min(dp[j][k],min(edges[k][i]+dp[i][j],edges[j][i]+dp[i][k]));
			}
		}
	}
	//for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cout<<i<<" "<<j<<": "<<dp[i][j]<<endl;
	int res=dp[U][V];
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			//if(dp[A][i]+dp[i][j]+dp[j][B]==dp[A][B] && (dp[U][i]+dp[i][j]+dp[j][V]==dp[U][V] || dp[V][i]+dp[i][j]+dp[j][U]==dp[U][V]))
			if(dp[A][i]+dp[i][j]+dp[j][B]==dp[A][B])
			{
				res=min(res,min(dp[U][i]+dp[j][V],dp[V][i]+dp[U][j]));
				//cout<<i<<" "<<j<<endl;
			}
			//if(dp[A][i]+dp[i][j]+dp[j][B]==dp[A][B] && dp[V][i]+dp[i][j]+dp[j][U]==dp[U][V]) res=max(res,dp[i][j]);
			//if(dp[B][i]+dp[i][j]+dp[j][A]==dp[A][B] && dp[U][i]+dp[i][j]+dp[j][V]==dp[U][V]) res=max(res,dp[i][j]);
			//if(dp[B][i]+dp[i][j]+dp[j][A]==dp[A][B] && dp[V][i]+dp[i][j]+dp[j][U]==dp[U][V]) res=max(res,dp[i][j]);
		}
	}
	//res=dp[U][V]-res;
	cout<<res<<endl;
    return 0;
}

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