Submission #1182726

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182726		nguyn	Robot (JOI21_ho_t4)	C++20	100 / 100	122 ms	23792 KiB

Main

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

#define int long long
#define ll long long 
#define F first
#define S second
#define pb push_back 
#define pii pair<int,int>
#define iii pair<int, pair<int, int>>

const int N = 2e5 + 5;
const int inf = 1e18;

struct Edge {
	int v, c, p;
};

int n, m; 
vector<Edge> g[N];
int d[N];
int cnt[N];
int mn[N];

signed main(){
    ios_base::sync_with_stdio(false) ; 
    cin.tie(0) ; cout.tie(0) ; 
    if (fopen("INP.INP" ,"r")) {
        freopen("INP.INP" ,"r" , stdin) ;
        freopen("OUT.OUT" , "w" , stdout) ;
    }
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
    	int u, v, c, p;
    	cin >> u >> v >> c >> p;
    	g[u].pb({v, c, p});
    	g[v].pb({u, c, p});
    }
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    for (int i = 1; i <= n; i++) d[i] = inf;;
    d[1] = 0;
	pq.push({0, 1});
	while(!pq.empty()) {
		int u = pq.top().S;
		int du = pq.top().F; 
		// int pre = pq.top().S.S;
		pq.pop();


		if (du != d[u]) continue;
		// cout << d[u] << ' ' << u << endl;
		for (auto it : g[u]) {
			cnt[it.c] = 0;
			mn[it.c] = inf;
		}
		for (auto it : g[u]) {
			cnt[it.c] += it.p;
		}
		for (auto it : g[u]) {
			mn[it.c] = min(mn[it.c], d[it.v] + cnt[it.c]); 
		}
		for (auto it : g[u]) {
			int v = it.v;	
			int c = it.c; 
			int p = it.p; 
			int w = min({d[u] + p, d[u] + cnt[it.c] - p, mn[it.c] - p});
			if (w < d[v]) {
				d[v] = w; 
				pq.push({d[v], v});
			}
		}
	}
	if (d[n] == inf) cout << -1;
	else cout << d[n];
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:29:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |         freopen("INP.INP" ,"r" , stdin) ;
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:30:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |         freopen("OUT.OUT" , "w" , stdout) ;
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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