Submission #331813

#	Time	Username	Problem	Language	Result	Execution time	Memory
331813		arnold518	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	637 ms	27024 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;
const ll INF = 1e18;

int N, M;
vector<pii> adj[MAXN+10];
int S, T, U, V;
ll DS[MAXN+10], DU[MAXN+10], DV[MAXN+10];

vector<int> adj2[MAXN+10];

struct Queue
{
	int u; ll w;
	bool operator < (const Queue &p) const
	{
		return w>p.w;
	}
};

void dijk(int S, ll *D)
{
	priority_queue<Queue> PQ;
	for(int i=1; i<=N; i++) D[i]=INF;
	PQ.push({S, 0});
	while(!PQ.empty())
	{
		Queue now=PQ.top(); PQ.pop();
		if(D[now.u]<=now.w) continue;
		D[now.u]=now.w;

		for(auto nxt : adj[now.u])
		{
			PQ.push({nxt.first, now.w+nxt.second});
		}
	}
}

bool vis[MAXN+10];
vector<int> ST;
void dfs(int now)
{
	vis[now]=true;
	for(int nxt : adj2[now])
	{
		if(vis[nxt]) continue;
		dfs(nxt);
	}
	ST.push_back(now);
}

ll dp[MAXN+10][4];

int main()
{
	scanf("%d%d", &N, &M);
	scanf("%d%d%d%d", &S, &T, &U, &V);

	for(int i=1; i<=M; i++)
	{
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		adj[u].push_back({v, w});
		adj[v].push_back({u, w});
	}

	dijk(S, DS);
	dijk(U, DU);
	dijk(V, DV);

	for(int now=1; now<=N; now++)
	{
		for(auto nxt : adj[now])
		{
			if(DS[nxt.first]==DS[now]+nxt.second)
			{
				adj2[now].push_back(nxt.first);
			}
		}
	}

	dfs(S);
	reverse(ST.begin(), ST.end());

	for(int i=1; i<=N; i++) for(int j=0; j<4; j++) dp[i][j]=INF;
	dp[S][0]=0;
	for(auto now : ST)
	{
		dp[now][1]=min(dp[now][1], dp[now][0]+DU[now]);
		dp[now][2]=min(dp[now][2], dp[now][0]+DV[now]);
		dp[now][3]=min({dp[now][3], dp[now][2]+DU[now], dp[now][1]+DV[now], dp[now][0]+DU[now]+DV[now]});

		for(auto nxt : adj2[now])
		{
			for(int j=0; j<4; j++)
			{
				dp[nxt][j]=min(dp[nxt][j], dp[now][j]);
			}
		}
	}
	printf("%lld\n", min(DU[V], dp[T][3]));
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:62:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   62 |  scanf("%d%d", &N, &M);
      |  ~~~~~^~~~~~~~~~~~~~~~
commuter_pass.cpp:63:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   63 |  scanf("%d%d%d%d", &S, &T, &U, &V);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:68:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   68 |   scanf("%d%d%d", &u, &v, &w);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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