Submission #1164665

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164665		mertbbm	Robot (JOI21_ho_t4)	C++20	0 / 100	3098 ms	91844 KiB

Main

#include <bits/stdc++.h>
using namespace std;
 
#define int long long 
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii;
typedef pair<int,pii>pi2;
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());

void solve(){
	int n,m;
	cin >> n >> m;
	
	int temp,temp2,temp3,temp4;
	vector<pair<int,pii>>adj[n+5];
	unordered_map<int,vector<pii>>adj2[n+5];
	map<pii,int>mp;
	
	for(int x=0;x<m;x++){
		cin >> temp >> temp2 >> temp3 >> temp4;
		
		adj[temp].push_back({temp2,{temp3,temp4}});
		adj[temp2].push_back({temp,{temp3,temp4}});
		mp[{temp,temp3}]+=temp4;
		mp[{temp2,temp3}]+=temp4;
		adj2[temp][temp3].push_back({temp2,temp4});
		adj2[temp2][temp3].push_back({temp,temp4});
	}
	
	unordered_map<int,int>dist[n+5];
	priority_queue<pi2,vector<pi2>,greater<pi2>>pq;
	
	dist[1][0]=0;
	pq.push({0,{1,0}});
	
	for(auto it:adj2[1]){
		dist[1][it.first]=mp[{1,it.first}];
		pq.push({mp[{1,it.first}],{1,it.first}});
	}
	
	while(!pq.empty()){
		pi2 cur=pq.top();
		pq.pop();
		int index=cur.second.first;
		int col=cur.second.second;
		int d=cur.first;
		//show3(index,index,col,col,d,d);
		if(dist[index][col]!=d) continue;
		if(col!=0){
			for(auto it:adj2[index][col]){
				int nx=it.first;
				int cost=it.second;
				int nd=d-cost;
				if(dist[nx].find(0)==dist[nx].end()||dist[nx][0]>nd){
					dist[nx][0]=nd;
					pq.push({nd,{nx,0}});
				}
			}
		}
		for(auto it:adj[index]){
			int nx=it.first;
			int a=it.second.first;
			int cost=it.second.second;
			//no charge
			int nd=d+cost;
			if(mp[{index,a}]==cost) nd=d;
			if(dist[nx].find(0)==dist[nx].end()||dist[nx][0]>nd){
				dist[nx][0]=nd;
				pq.push({nd,{nx,0}});
			}
			
			//charge
			nd=d+mp[{nx,a}];
			if(dist[nx].find(a)==dist[nx].end()||dist[nx][a]>nd){
				dist[nx][a]=nd;
				pq.push({nd,{nx,a}});
			}
		}
	}
	
	int best=1e18;
	for(int x=0;x<=m;x++){
		if(dist[n].find(x)!=dist[n].end()){
			best=min(best,dist[n][x]);
		}
	}
	if(best==1e18) cout << -1;
	else cout << best;
}

int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	int t=1;	
	//cin >> t;	
	while(t--){
		solve(); 
	}
}

• Subtask 1: 0 / 34
• Subtask 2: 0 / 24
• Subtask 3: 0 / 42