Submission #377289

#	Time	Username	Problem	Language	Result	Execution time	Memory
377289		YJU	Robot (JOI21_ho_t4)	C++14	100 / 100	1100 ms	82992 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n, m;
struct node {
	ll dis;
	int u, c;
	node() {}
	node(int _u, int _c, ll _d) { u = _u, c = _c, dis = _d; }
	friend bool operator < (node a, node b) { return a.dis > b.dis; }
};
priority_queue<node> Q;

const int maxn = 100005;
const int maxm = 400005;

int last[maxn], Next[maxm], to[maxm], w[maxm], col[maxm], cnt;
unordered_map <int, ll> Map[maxn], sum[maxn];
unordered_map <int, vector<pair<int, int> > > out[maxn];

inline void addedge(int x, int y, int z, int c) {
	Next[++cnt] = last[x], last[x] = cnt; 
	to[cnt] = y, w[cnt] = z, col[cnt] = c;
	out[x][c].push_back(make_pair(y, z));
	sum[x][c] += z;
} 


int main() {
	scanf("%d%d", &n, &m);
	for(int i = 1, x, y, z, c; i <= m; i++) {
		scanf("%d%d%d%d", &x, &y, &c, &z);
		addedge(x, y, z, c), addedge(y, x, z, c);
	} 
	auto check = [=] (int u, int c, ll dis) -> void {
		if(!Map[u].count(c) || Map[u][c] > dis) 
			Map[u][c] = dis, Q.push(node(u, c, dis));
	};
	
	check(1, 0, 0);
	while(!Q.empty()) {
		node tmp = Q.top();
		Q.pop();
		int u = tmp.u, c = tmp.c;
		ll dis = tmp.dis;
		if(Map[u][c] != dis) continue;
		
		if(!c) {
			for(int i = last[u]; i; i = Next[i]) {
				int v = to[i];
				check(v, col[i], dis);
				check(v, 0, dis + min(sum[u][col[i]] - w[i], (ll)w[i]));
			}
		}
		else {
			if(out[u].count(c)) {
				for(auto tp : out[u][c]) {
					int v = tp.first, w = tp.second;
					check(v, 0, dis + sum[u][c] - w);
				}
			}
		}
	}
	
	Map[n].count(0) ? printf("%lld\n", Map[n][0]) : puts("-1");
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:30:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   30 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:32:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   32 |   scanf("%d%d%d%d", &x, &y, &c, &z);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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