Submission #860278

#	Time	Username	Problem	Language	Result	Execution time	Memory
860278		StefanSebez	Commuter Pass (JOI18_commuter_pass)	C++14	0 / 100	803 ms	45796 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];
map<pair<int,int>,int>edges;
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}]=edges[{v,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});
				}
			}
		}
		for(int i=1;i<=n;i++)
		{
			dp[j][i]=dist[i];
		}
	}*/
	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[A]=0;
	pq.push({0,A});
	int parent[n+1];
	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});
				parent[i.fi]=x.se;
			}
		}
	}
	int C=B;
	while(C!=A)
	{
		//cout<<C<<" ";
		int x=parent[C];
		edges[{x,C}]=edges[{C,x}]=0;
		C=x;
	}
	//cout<<endl;
	//for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cout<<i<<" "<<j<<": "<<edges[{i,j}]<<" "<<edges[{j,i}]<<endl;

	for(int i=1;i<=n;i++)was[i]=false;
	for(int i=1;i<=n;i++) dist[i]=inf;
	while(!pq.empty()) pq.pop();
	dist[U]=0;
	pq.push({0,U});
	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+edges[{i.fi,x.se}]);
				pq.push({-dist[i.fi],i.fi});
			}
		}
	}
	//for(int i=1;i<=n;i++) cout<<dist[i]<<" ";
	//cout<<endl;
	int res=dist[V];

	/*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]) res=min(res,min(dp[U][i]+dp[j][V],dp[V][i]+dp[U][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