Submission #860274

#	Time	Username	Problem	Language	Result	Execution time	Memory
860274		StefanSebez	Commuter Pass (JOI18_commuter_pass)	C++14	24 / 100	1651 ms	262144 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define int long long
#define fi first
#define se second
const int N=1e5+50;
const int inf=1e15;
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 j=1;j<=n;j++)
	{
		int dist[n+1];
		bool was[n+1]={0};
		priority_queue<pair<int,int> >pq;
		for(int i=1;i<=n;i++) dist[i]=inf;
		dist[j]=0;
		pq.push({0,j});
		while(!pq.empty())
		{
			pair<int,int> x=pq.top();
			pq.pop();
			if(was[x.se]) continue;
			was[x.se]=true;
			for(auto i:E[x.se])
			{
				if(!was[i.fi])
				{
					dist[i.fi]=min(dist[i.fi],-x.fi+i.se);
					pq.push({-dist[i.fi],i.fi});
				}
			}
		}
		//cout<<j<<": ";
		for(int i=1;i<=n;i++)
		{
			dp[j][i]=dist[i];
			//cout<<dist[i]<<" ";
		}
		//cout<<endl;
	}

	/*int dp1[n+1][n+1];
	for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) dp1[i][j]=inf;
	for(int i=1;i<=n;i++) edges[i][i]=0;
	for(int i=1;i<=n;i++)
	{
		dp1[i][i]=0;
		for(int j=1;j<=i;j++)
		{
			for(int k=1;k<i;k++)
			{
				dp1[i][j]=min(dp1[i][j],edges[i][k]+dp1[k][j]);
			}
			dp1[j][i]=dp1[i][j];
		}
		for(int j=1;j<i;j++)
		{
			for(int k=1;k<i;k++)
			{
				dp1[j][k]=min(dp1[j][k],min(edges[k][i]+dp1[i][j],edges[j][i]+dp1[i][k]));
			}
		}
	}

	for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(dp[i][j]!=dp1[i][j]) cout<<i<<" "<<j<<": "<<dp[i][j]<<" "<<dp1[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;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:15:9: warning: variable 'edges' set but not used [-Wunused-but-set-variable]
   15 |     int edges[n+1][n+1];
      |         ^~~~~

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