oj.uz

답안 #484771

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
484771 2021-11-05T11:53:27 Z BackNoob Robot (JOI21_ho_t4) C++14
100 / 100
 743 ms 89940 KB 
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define endl '\n'
#define MASK(i) (1LL << (i))
#define ull unsigned long long
#define ld long double
#define pb push_back
#define all(x) (x).begin() , (x).end()
#define BIT(x , i) ((x >> (i)) & 1) 
#define TASK "task"
#define sz(s) (int) (s).size()
 
using namespace std;
const int mxN = 3e5 + 227;
const int inf = 1e9 + 277;
const int mod = 1e9 + 7;
const ll infll = 1e18 + 7;
const int base = 307;
const int LOG = 20;
 
template <typename T1, typename T2> bool minimize(T1 &a, T2 b) {
	if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b) {
	if (a < b) {a = b; return true;} return false;
}
 
struct item{
	int u;
	int pre;
	ll d;
};
 
struct cmp{
	bool operator()(const item &a , const item &b)
	{
		return a.d > b.d;
	}
};
 
struct EDGE{
	int v , color , cost;
};
 
int n , m;
vector<EDGE> adj[mxN];
ll dist[mxN];
map<int , ll> dp[mxN];
int cnt[mxN];
ll sumcost[mxN];
map<int , vector<pair<int , int>>> adjcolor[mxN]; 
 
void solve()
{
	cin >> n >> m;
	for(int i = 1 ; i <= m ; i++) {
		int u , v , color , cost;
		cin >> u >> v >> color >> cost;
		adj[u].pb({v , color , cost});
		adj[v].pb({u , color , cost});
		adjcolor[u][color].pb({v , cost});
		adjcolor[v][color].pb({u , cost});
	}
 	
	memset(dist , 0x3f , sizeof(dist));
	priority_queue<item , vector<item> , cmp> pq;
	pq.push({1 , 0 , dist[1] = 0});
	while(!pq.empty()) {
		int u , pre;
		ll d;
		u = pq.top().u;
		pre = pq.top().pre;
		d = pq.top().d;
		pq.pop();
 
		if(pre == 0 && dist[u] != d) continue;
		if(pre != 0 && dp[u][pre] != d) continue;
 
 
		if(pre == 0) {
			for(auto it : adj[u]) sumcost[it.color] += it.cost;
			for(auto it : adj[u]) {
				if(!dp[it.v].count(it.color) || dp[it.v][it.color] > d) {
					dp[it.v][it.color] = d;
					pq.push({it.v , it.color , d});
				}
				if(minimize(dist[it.v] , d + sumcost[it.color] - it.cost) == true) {
					pq.push({it.v , 0 , d + sumcost[it.color] - it.cost});
				}
				if(minimize(dist[it.v] , d + it.cost) == true) {
					pq.push({it.v , 0 , d + it.cost});
				}
			}
			for(auto it : adj[u]) sumcost[it.color] -= it.cost;
		}
		if(pre != 0) {
			for(auto it : adjcolor[u][pre]) sumcost[pre] += it.se;
			for(auto it : adjcolor[u][pre]) { 
 
				if(minimize(dist[it.fi] , d + sumcost[pre] - it.se) == true) {
					pq.push({it.fi , 0 , d + sumcost[pre] - it.se});
				}
			}
			for(auto it : adjcolor[u][pre]) sumcost[pre] -= it.se;
		}
 
	}
	ll ans = dist[n];
	if(ans == dist[0]) cout << -1;
	else cout << ans;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    //freopen(TASK".inp" , "r" , stdin);
    //freopen(TASK".out" , "w" , stdout);
    
    int tc = 1;
    //cin >> tc;
    while(tc--) {
    	solve();
    }
    return 0;
}

Subtask #1
34.0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 37836 KB Output is correct
2 Correct 16 ms 37872 KB Output is correct
3 Correct 16 ms 37864 KB Output is correct
4 Correct 16 ms 37848 KB Output is correct
5 Correct 16 ms 37836 KB Output is correct
6 Correct 16 ms 37856 KB Output is correct
7 Correct 17 ms 37992 KB Output is correct
8 Correct 17 ms 37964 KB Output is correct
9 Correct 25 ms 38436 KB Output is correct
10 Correct 19 ms 38348 KB Output is correct
11 Correct 18 ms 38128 KB Output is correct
12 Correct 18 ms 38092 KB Output is correct
13 Correct 20 ms 38220 KB Output is correct
14 Correct 17 ms 38220 KB Output is correct
15 Correct 18 ms 38132 KB Output is correct
16 Correct 20 ms 38112 KB Output is correct
17 Correct 17 ms 38224 KB Output is correct
18 Correct 17 ms 37964 KB Output is correct
19 Correct 17 ms 38092 KB Output is correct
20 Correct 17 ms 38092 KB Output is correct

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 164 ms 53768 KB Output is correct
2 Correct 65 ms 45856 KB Output is correct
3 Correct 156 ms 52256 KB Output is correct
4 Correct 93 ms 48404 KB Output is correct
5 Correct 724 ms 89496 KB Output is correct
6 Correct 587 ms 82644 KB Output is correct
7 Correct 255 ms 69644 KB Output is correct
8 Correct 333 ms 66456 KB Output is correct
9 Correct 391 ms 66424 KB Output is correct
10 Correct 241 ms 63508 KB Output is correct
11 Correct 118 ms 51036 KB Output is correct

Subtask #3
42.0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 37836 KB Output is correct
2 Correct 16 ms 37872 KB Output is correct
3 Correct 16 ms 37864 KB Output is correct
4 Correct 16 ms 37848 KB Output is correct
5 Correct 16 ms 37836 KB Output is correct
6 Correct 16 ms 37856 KB Output is correct
7 Correct 17 ms 37992 KB Output is correct
8 Correct 17 ms 37964 KB Output is correct
9 Correct 25 ms 38436 KB Output is correct
10 Correct 19 ms 38348 KB Output is correct
11 Correct 18 ms 38128 KB Output is correct
12 Correct 18 ms 38092 KB Output is correct
13 Correct 20 ms 38220 KB Output is correct
14 Correct 17 ms 38220 KB Output is correct
15 Correct 18 ms 38132 KB Output is correct
16 Correct 20 ms 38112 KB Output is correct
17 Correct 17 ms 38224 KB Output is correct
18 Correct 17 ms 37964 KB Output is correct
19 Correct 17 ms 38092 KB Output is correct
20 Correct 17 ms 38092 KB Output is correct
21 Correct 164 ms 53768 KB Output is correct
22 Correct 65 ms 45856 KB Output is correct
23 Correct 156 ms 52256 KB Output is correct
24 Correct 93 ms 48404 KB Output is correct
25 Correct 724 ms 89496 KB Output is correct
26 Correct 587 ms 82644 KB Output is correct
27 Correct 255 ms 69644 KB Output is correct
28 Correct 333 ms 66456 KB Output is correct
29 Correct 391 ms 66424 KB Output is correct
30 Correct 241 ms 63508 KB Output is correct
31 Correct 118 ms 51036 KB Output is correct
32 Correct 162 ms 48768 KB Output is correct
33 Correct 143 ms 49904 KB Output is correct
34 Correct 347 ms 65344 KB Output is correct
35 Correct 290 ms 58736 KB Output is correct
36 Correct 256 ms 60812 KB Output is correct
37 Correct 312 ms 63260 KB Output is correct
38 Correct 255 ms 69148 KB Output is correct
39 Correct 198 ms 52292 KB Output is correct
40 Correct 353 ms 66612 KB Output is correct
41 Correct 375 ms 66440 KB Output is correct
42 Correct 421 ms 72940 KB Output is correct
43 Correct 159 ms 54712 KB Output is correct
44 Correct 328 ms 60376 KB Output is correct
45 Correct 306 ms 63192 KB Output is correct
46 Correct 258 ms 62936 KB Output is correct
47 Correct 285 ms 62524 KB Output is correct
48 Correct 743 ms 89940 KB Output is correct