Submission #1182709

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182709		nguyn	Robot (JOI21_ho_t4)	C++20	0 / 100	107 ms	20532 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>

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];

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; 
		pq.pop();


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

Compilation message (stderr)

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

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