Submission #544964

#	Time	Username	Problem	Language	Result	Execution time	Memory
544964		inluminas	Olympic Bus (JOI20_ho_t4)	C++14	0 / 100	21 ms	4044 KiB

ho_t4

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

#define ll long long
#define endl "\n"
#define fastio ios_base::sync_with_stdio(false)
#define inf LLONG_MAX

const int lmt=202;
vector<pair<ll,ll>>adj[lmt][2];
ll dis[lmt][2][2];

int main(){
	fastio;

	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		ll u,v,c,d;
		cin>>u>>v>>c>>d;
		adj[u][0].push_back({c,v});
		adj[v][1].push_back({c+d,u});
	}

	for(int i=0;i<=n;i++){
		for(int j=0;j<2;j++) for(int k=0;k<2;k++) dis[i][j][k]=inf;
	}

	set<array<ll,4>>q;
	q.insert({0,1,0,0});

	while(!q.empty()){
		auto it=q.begin();
		ll val=(*it)[0],u=(*it)[1],ver=(*it)[2],ver2=(*it)[3];

		q.erase(it);

		if(dis[u][ver][ver2]<val) continue;

		for(auto [w,v]:adj[u][0]){
			if(v==n){
				if(dis[v][ver][1]>val+w){
					q.erase({dis[v][ver][1],v,ver,1});
					dis[v][ver][1]=val+w;
					q.insert({dis[v][ver][1],v,ver,1});
				}
			}else{
				if(dis[v][ver][ver2]>val+w){
					q.erase({dis[v][ver][ver2],v,ver,ver2});
					dis[v][ver][ver2]=val+w;
					q.insert({dis[v][ver][ver2],v,ver,ver2});
				}
			}
		}

		if(ver) continue;

		for(auto [w,v]:adj[u][1]){
			if(v==n){
				if(dis[v][1][1]>val+w){
					q.erase({dis[v][1][1],v,1,1});
					dis[v][1][1]=val+w;
					q.insert({dis[v][ver][1],v,1,1});
				}
			}else{
				if(dis[v][1][ver2]>val+w){
					q.erase({dis[v][1][ver2],v,1,ver2});
					dis[v][1][ver2]=val+w;
					q.insert({dis[v][1][ver2],v,1,ver2});
				}
			}
		}
	}

	ll ans=min(dis[1][0][1],dis[1][1][1]);
	if(ans==inf) ans=-1;

	cout<<ans<<endl;
	return 0;
}

Compilation message (stderr)

ho_t4.cpp: In function 'int main()':
ho_t4.cpp:40:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   40 |   for(auto [w,v]:adj[u][0]){
      |            ^
ho_t4.cpp:58:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   58 |   for(auto [w,v]:adj[u][1]){
      |            ^

• Subtask 1: 0 / 5
• Subtask 2: 0 / 11
• Subtask 3: 0 / 21
• Subtask 4: 0 / 63