Submission #1294096

#	Time	Username	Problem	Language	Result	Execution time	Memory
1294096		tunademayo	Robot (JOI21_ho_t4)	C++20	100 / 100	89 ms	15048 KiB

Main

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

#define ll long long 
#define fi first
#define se second

const bool Multitest = 0, Local = 0;
const int N = 2e5 + 10;

int n, m; 
vector<pair<int, pair<int, int>>> adj[N];
ll d[N], s[N], mi[N]; bitset<N> vis;

struct Data
{
	int u; ll w;
	
	Data( ) { }
	Data(int _u, ll _w) : u(_u), w(_w) { }
}; 
#define Push(u, w) push(Data(u, w))
struct cmp
{
	bool operator () (Data a, Data b)
	{
		return a.w > b.w;
	}
};

void work()
{
	cin >> n >> m;
	
	for(int i = 1 ; i <= m ; i++)
	{
		int u, v, c, w;	cin >> u >> v >> c >> w;
		adj[u].push_back({v, {c, w}});
		adj[v].push_back({u, {c, w}});
	}
	
	for(int i = 1 ; i <= n ; i++) d[i] = 1e18;
	for(int i = 1 ; i <= m ; i++) mi[i] = 1e18;
	priority_queue<Data, vector<Data>, cmp> q;
	q.Push(1, 0); d[1] = 0;
	
	while(!q.empty())
	{
		Data x = q.top(); q.pop();
		
		if(vis[x.u]) continue;
		vis[x.u] = 1;
		
//		cerr << x.u << ' ' << x.w << '\n';
		
		for(int i = 0 ; i < adj[x.u].size() ; i++)
		{
			int v = adj[x.u][i].fi, c = adj[x.u][i].se.fi, w = adj[x.u][i].se.se;
			s[c] += w;
		}
		
		for(int i = 0 ; i < adj[x.u].size() ; i++)
		{
			int v = adj[x.u][i].fi, c = adj[x.u][i].se.fi, w = adj[x.u][i].se.se;
			mi[c] = min(mi[c], d[v] + s[c]);
		}
		
		for(int i = 0 ; i < adj[x.u].size() ; i++)
		{
			int v = adj[x.u][i].fi, c = adj[x.u][i].se.fi, w = adj[x.u][i].se.se;
			
			ll val = x.w + min((ll)w, s[c] - w);
			val = min(val, mi[c] - w);
			
			if(d[v] > val)
			{
				d[v] = val;
				q.Push(v, d[v]);
			}
		}
		
		for(int i = 0 ; i < adj[x.u].size() ; i++)
		{
			int v = adj[x.u][i].fi, c = adj[x.u][i].se.fi, w = adj[x.u][i].se.se;
			s[c] = 0, mi[c] = 1e18;
		}
	}
	
	cout << (d[n] == 1e18 ? -1 : d[n]);
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);	cout.tie(0);
	
	if(Local && fopen("code.inp", "r"))
	{
		freopen("code.inp", "r", stdin);
		freopen("code.out", "w", stdout);
	}
	
	int q = 1;
	
	if(Multitest) cin >> q;
	
	while(q--) work();
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:99:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |                 freopen("code.inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:100:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  100 |                 freopen("code.out", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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