Submission #228972

#	Time	Username	Problem	Language	Result	Execution time	Memory
228972		bharat2002	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	637 ms	36600 KiB

commuter_pass

/*input
5 5
1 5
2 3
1 2 1
2 3 10
2 4 10
3 5 10
4 5 10
*/
#include<bits/stdc++.h>
using namespace std;
const int N=1e5 + 100;
const int mod=1e9 + 7;
#define int long long
const int inf=1e18;
#define pii pair<int, int>
#define f first
#define s second 
#define mp make_pair
#define FOR(i, n) for(int i=1;i<=n;i++)
#define TRACE(x) cerr << #x << " = " << x << endl 
//Trace prints the name of the variable and the value.
int n, m, s, t, u, v, dists[N], distt[N];
vector< pii > adjlist[N];
priority_queue< pii, vector<pii>, greater<pii> >pq1;int dp[N][4];
void dij(int src, int dist[N])
{
	for(int i=1;i<=n;i++) {dist[i]=inf;dp[i][0]=dp[i][1]=dp[i][2]=dp[i][3]=inf;}
	dist[src]=0;pq1.push(mp(0, src));
	while(!pq1.empty())
	{
		pii cur=pq1.top();pq1.pop();
		if(cur.f>dist[cur.s]) continue;
		for(auto j:adjlist[cur.s])
		{
			if(dist[j.f]>cur.f + j.s)
			{
				dist[j.f]=cur.f+j.s;pq1.push(mp(dist[j.f], j.f));
			}
		}
	}
}
struct node
{
	int i, j, cd;
};
node mn(int a, int b, int c)
{
	node t;t.i=a;t.j=b;t.cd=c;return t;
}
struct comp
{
	bool operator()(node a, node b)
	{
		if(a.cd==b.cd) return (b.j==1);
		return a.cd>=b.cd;
	}
};
priority_queue<node, vector<node>, comp> pq;
signed main()
{
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	cin>>n>>m>>s>>t>>u>>v;
	for(int i=1;i<=m;i++)
	{
		int u, v, w;cin>>u>>v>>w;adjlist[u].push_back(mp(v, w));adjlist[v].push_back(mp(u, w));
	}
	dij(s, dists);dij(t, distt);
	dp[u][0]=dp[u][1]=dp[u][2]=dp[u][3]=0;pq.push(mn(u, 0, 0));pq.push(mn(u, 1, 0));pq.push(mn(u, 2, 0));
	while(!pq.empty())
	{

		node cur=pq.top();pq.pop();//cout<<cur.i<<" "<<cur.j<<endl;
		if(cur.cd>dp[cur.i][cur.j]) continue;
		for(auto j:adjlist[cur.i])
		{
			bool check=(dists[cur.i]+j.s+distt[j.f]==dists[t]||distt[cur.i]+j.s+dists[j.f]==dists[t]);
			if(cur.j==1) {
				if(check&&dists[j.f]<dists[cur.i]) {j.s=0;
					if(dp[j.f][1]>cur.cd +j.s)
					{
						dp[j.f][1]=cur.cd +j.s;pq.push(mn(j.f, 1, cur.cd +j.s));
					}
				}
			}
			if(cur.j==2)
			{
				if(check&&dists[j.f]>dists[cur.i]) {j.s=0;
					if(dp[j.f][2]>cur.cd +j.s)
					{
						dp[j.f][2]=cur.cd +j.s;pq.push(mn(j.f, 2, cur.cd +j.s));
					}
				}
			}
			if(cur.j==0)
			{
				for(int nxt=0;nxt<3;nxt++)
				{
					if(dp[j.f][nxt]>cur.cd +j.s)
					{
						dp[j.f][nxt]=cur.cd +j.s;pq.push(mn(j.f, nxt, cur.cd +j.s));
					}
				}
			}
			if(dp[j.f][3]>cur.cd +j.s)
			{
				dp[j.f][3]=cur.cd +j.s;pq.push(mn(j.f, 3, cur.cd +j.s));continue;
			}
		}
	}
	cout<<min(min(dp[v][1], dp[v][2]), dp[v][3]);
}

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