Submission #706307

#	Time	Username	Problem	Language	Result	Execution time	Memory
706307		qwerasdfzxcl	Robot (JOI21_ho_t4)	C++17	100 / 100	352 ms	61908 KiB

Main

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
constexpr ll INF = 4e18;

int n, m;
vector<array<int, 3>> adj[100100];
vector<pair<int, ll>> G[500500];
vector<pair<int, int>> P;

ll dist[500500];

int getidx(int x, int y){
	return lower_bound(P.begin(), P.end(), pair<int, int>(x, y)) - P.begin() + n + 1;
}

void dijkstra(int s, int SZ){
	fill(dist+1, dist+SZ+1, INF);
	dist[s] = 0;
	priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
	pq.emplace(0, s);

	while(!pq.empty()){
		auto [d, s] = pq.top(); pq.pop();
		if (d > dist[s]) continue;
		assert(d == dist[s]);

		for (auto &[v, w]:G[s]) if (dist[v] > dist[s] + w){
			dist[v] = dist[s] + w;
			pq.emplace(dist[v], v);
		}
	}
}

int main(){
	scanf("%d %d", &n, &m);
	for (int i=1;i<=m;i++){
		int x, y, z, w;
		scanf("%d %d %d %d", &x, &y, &z, &w);
		adj[x].push_back({y, z, w});
		adj[y].push_back({x, z, w});
	}

	for (int i=1;i<=n;i++){
		sort(adj[i].begin(), adj[i].end(), [&](const array<int, 3> &x, const array<int, 3> &y){
			return x[1] < y[1];
		});
		for (auto &x:adj[i]) P.emplace_back(i, x[1]);
	}

	P.erase(unique(P.begin(), P.end()), P.end());

	for (int i=1;i<=n;i++){
		
		for (int j=0,r=0;j<(int)adj[i].size();j=r){
			while(r<(int)adj[i].size() && adj[i][j][1]==adj[i][r][1]) ++r;
			
			ll S = 0;
			for (int k=j;k<r;k++) S += adj[i][k][2];

			int i2 = getidx(i, adj[i][j][1]);
			for (int k=j;k<r;k++){
				auto [v, c, w] = adj[i][k];
				G[i].emplace_back(v, min((ll)w, S - w));
				G[i].emplace_back(getidx(v, c), 0);
				G[i2].emplace_back(v, S - w);
			}
		}
	}

	dijkstra(1, n+P.size());
	printf("%lld\n", dist[n]==INF?-1:dist[n]);
}

Compilation message (stderr)

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

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