Submission #1180852

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180852		ZeroCool	Robot (JOI21_ho_t4)	C++20	100 / 100	143 ms	21664 KiB

Main

#include <bits/stdc++.h>
using namespace std;;
#define ll long long
#define ar array
#define ld long double
#define int long long
#define all(v) v.begin(), v.end()

const int N = 1e5 + 20;
const int K = 469;
const int LOG = 21;
const int INF = 1e16;	
int MOD = 1e9 + 7;

template<typename T>
void chmin(T &x,T y){x = min(x, y);}
template<typename T>
void chmax(T &x,T y){x = max(x, y);}
void mm(int &x){x = (x % MOD + MOD) % MOD;};




void orz(){
	int n, m;
	cin>>n>>m;
	vector<ar<int, 3> >g[n];
	for(int i = 0;i < m;i++){
		int a, b, c, d;
		cin>>a>>b>>c>>d;
		--a, --b, --c;
		g[a].push_back({b, c, d});
		g[b].push_back({a, c, d});
	}
	priority_queue<ar<int, 2> > pq;
	pq.push({0, 0});
	bool vis[n];
	int dst[n];
	memset(vis, 0, sizeof vis);
	memset(dst, 0x3f, sizeof dst);
	dst[0] = 0;
	int s[m], p[m];
	while(pq.size()){
		auto [d, x] = pq.top();
		pq.pop();
		if(vis[x])continue;
		vis[x] = 1;
		//cout<<d<<": "<<x<<'\n';
		for(auto [u, a, b]: g[x])p[a] = INF, s[a] = 0;
		for(auto [u, a, b]: g[x])s[a] += b;
		for(auto [u, a, b]: g[x])chmin(p[a], dst[u] + s[a]);
		for(auto [u, a, b]: g[x]){
			int w = min({dst[x] + b, dst[x] + s[a] - b, p[a] - b});
			if(w < dst[u]){
				dst[u] = w;
				pq.push({-dst[u], u});
			}
		}
	}
	if(dst[n - 1] >= INF)cout<<-1;
	else cout<<dst[n - 1];
}	

signed main(){ios_base::sync_with_stdio(false);cin.tie(0);
	
	int t = 1;
	//cin>>t;
	//t = 1;
	while(t--)orz();
}
	

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