Submission #1257494

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257494		Bui_Quoc_Cuong	Robot (JOI21_ho_t4)	C++20	0 / 100	3095 ms	48040 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = a; i <= (int)b; i++)
#define FORD(i, a, b) for(int i = a; i >= (int)b; i--)
#define fi first
#define se second
const int N = 1E5 + 5;

int n, m;
vector <array <int, 3>> g[N];
map <int, long long> sumC[N];
map <int, long long> dp[N];

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    #define ko "kieuoanh"
    if (fopen(ko".inp", "r")) {
    	freopen(ko".inp", "r", stdin); freopen(ko".out", "w", stdout);
    }
    cin >> n >> m;
    FOR(i, 1, m) {
    	int u, v, c, p; cin >> u >> v >> c >> p;
    	sumC[u][c]+= p;
    	sumC[v][c]+= p;
    	g[u].push_back({c, v, p});
    	g[v].push_back({c, u, p});
    }
    FOR(i, 1, n) sort(g[i].begin(), g[i].end());

    #define bg array <long long, 3>
    priority_queue <bg, vector <bg>, greater <bg>> pq;
    pq.push({dp[1][0] = 0, 1, 0});

    while (!pq.empty()) {
    	int u = pq.top()[1], t = pq.top()[2];
    	long long cost = pq.top()[0];
    	pq.pop();
    	if (cost > dp[u][t]) continue;
    	if (t == 0) {
    		for (auto it : g[u]) {
    			int c = it[0], v = it[1], p = it[2];
    			if (dp[v].count(0) == 0) dp[v][0] = 1e18;
    			if (dp[v].count(c) == 0) dp[v][c] = 1e18;
    			if (dp[v][0] > cost + min(sumC[u][c] - p, 1LL * p)) {
    				dp[v][0] = cost + min(sumC[u][c] - p, 1LL * p);
    				pq.push({dp[v][0], v, 0});
    			}
    			if (dp[v][c] > cost) {
    				pq.push({dp[v][c] = cost, v, c});
    			}
    		}
    	} else {	
    		for (auto it : g[u]) {
    			int c = it[0], v = it[1], p = it[2];
    			if (c != t) continue;
    			if (dp[v].count(0) == 0) dp[v][0] = 1e18;
    			if (dp[v][0] > cost + sumC[u][c] - p) {
    				dp[v][0] = cost + sumC[u][c];
    				pq.push({dp[v][0], v, 0});
    			}
    		}
    	}
    }

    if (dp[n].count(0) == 0) {
    	cout << - 1;
    } else cout << dp[n][0];

    return 0;
}

Compilation message (stderr)

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

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