oj.uz

답안 #484770

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
484770 2021-11-05T11:52:07 Z BackNoob Robot (JOI21_ho_t4) C++14
100 / 100
 986 ms 145996 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 EDGE{
	int v , color , cost;
};
 
int n , m;
vector<EDGE> adj[mxN];
ll dist[mxN];
unordered_map<int , ll> dp[mxN];
int cnt[mxN];
unordered_map<int , ll> sumcost[mxN];
unordered_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});
		sumcost[u][color] += cost;
		sumcost[v][color] += cost;
	}
 	
	memset(dist , 0x3f , sizeof(dist));
	priority_queue <tuple <ll, int, int>, vector <tuple <ll, int, int>>, greater <tuple <ll, int, int>>> pq;
	pq.push({dist[1] = 0 , 1 , 0});
	while(!pq.empty()) {
		int u , pre;
		ll d;
		tie(d , u , pre) = pq.top();
		pq.pop();
 
		if(pre == 0 && dist[u] != d) continue;
 

		if(pre == 0) {
			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({d , it.v , it.color});
				}
				if(minimize(dist[it.v] , d + sumcost[u][it.color] - it.cost) == true) {
					pq.push({d + sumcost[u][it.color] - it.cost , it.v , 0});
				}
				if(minimize(dist[it.v] , d + it.cost) == true) {
					pq.push({d + it.cost , it.v , 0});
				}
			}
		}
		if(pre != 0) {
			if(pre != 0 && dp[u][pre] != d) continue;
			for(auto it : adjcolor[u][pre]) { 

				if(minimize(dist[it.fi] , d + sumcost[u][pre] - it.se) == true) {
					pq.push({d + sumcost[u][pre] - it.se , it.fi , 0});
				}
			}
		}
 
	}
	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 30 ms 58948 KB Output is correct
2 Correct 29 ms 59016 KB Output is correct
3 Correct 29 ms 58976 KB Output is correct
4 Correct 30 ms 59072 KB Output is correct
5 Correct 30 ms 59100 KB Output is correct
6 Correct 30 ms 59084 KB Output is correct
7 Correct 30 ms 59204 KB Output is correct
8 Correct 31 ms 59124 KB Output is correct
9 Correct 32 ms 59860 KB Output is correct
10 Correct 34 ms 59836 KB Output is correct
11 Correct 33 ms 59672 KB Output is correct
12 Correct 33 ms 59552 KB Output is correct
13 Correct 33 ms 59616 KB Output is correct
14 Correct 33 ms 59596 KB Output is correct
15 Correct 32 ms 59540 KB Output is correct
16 Correct 34 ms 59648 KB Output is correct
17 Correct 34 ms 59548 KB Output is correct
18 Correct 32 ms 59340 KB Output is correct
19 Correct 32 ms 59312 KB Output is correct
20 Correct 33 ms 59492 KB Output is correct

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 230 ms 80944 KB Output is correct
2 Correct 121 ms 70960 KB Output is correct
3 Correct 269 ms 77408 KB Output is correct
4 Correct 171 ms 76084 KB Output is correct
5 Correct 879 ms 140300 KB Output is correct
6 Correct 755 ms 131096 KB Output is correct
7 Correct 455 ms 123568 KB Output is correct
8 Correct 585 ms 119908 KB Output is correct
9 Correct 606 ms 120004 KB Output is correct
10 Correct 421 ms 100076 KB Output is correct
11 Correct 232 ms 90352 KB Output is correct

Subtask #3
42.0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 58948 KB Output is correct
2 Correct 29 ms 59016 KB Output is correct
3 Correct 29 ms 58976 KB Output is correct
4 Correct 30 ms 59072 KB Output is correct
5 Correct 30 ms 59100 KB Output is correct
6 Correct 30 ms 59084 KB Output is correct
7 Correct 30 ms 59204 KB Output is correct
8 Correct 31 ms 59124 KB Output is correct
9 Correct 32 ms 59860 KB Output is correct
10 Correct 34 ms 59836 KB Output is correct
11 Correct 33 ms 59672 KB Output is correct
12 Correct 33 ms 59552 KB Output is correct
13 Correct 33 ms 59616 KB Output is correct
14 Correct 33 ms 59596 KB Output is correct
15 Correct 32 ms 59540 KB Output is correct
16 Correct 34 ms 59648 KB Output is correct
17 Correct 34 ms 59548 KB Output is correct
18 Correct 32 ms 59340 KB Output is correct
19 Correct 32 ms 59312 KB Output is correct
20 Correct 33 ms 59492 KB Output is correct
21 Correct 230 ms 80944 KB Output is correct
22 Correct 121 ms 70960 KB Output is correct
23 Correct 269 ms 77408 KB Output is correct
24 Correct 171 ms 76084 KB Output is correct
25 Correct 879 ms 140300 KB Output is correct
26 Correct 755 ms 131096 KB Output is correct
27 Correct 455 ms 123568 KB Output is correct
28 Correct 585 ms 119908 KB Output is correct
29 Correct 606 ms 120004 KB Output is correct
30 Correct 421 ms 100076 KB Output is correct
31 Correct 232 ms 90352 KB Output is correct
32 Correct 156 ms 73956 KB Output is correct
33 Correct 260 ms 79932 KB Output is correct
34 Correct 479 ms 100108 KB Output is correct
35 Correct 399 ms 93888 KB Output is correct
36 Correct 451 ms 114468 KB Output is correct
37 Correct 532 ms 117336 KB Output is correct
38 Correct 495 ms 122372 KB Output is correct
39 Correct 240 ms 80312 KB Output is correct
40 Correct 639 ms 121328 KB Output is correct
41 Correct 640 ms 121412 KB Output is correct
42 Correct 648 ms 122008 KB Output is correct
43 Correct 251 ms 83008 KB Output is correct
44 Correct 424 ms 86944 KB Output is correct
45 Correct 518 ms 117240 KB Output is correct
46 Correct 483 ms 116036 KB Output is correct
47 Correct 465 ms 116984 KB Output is correct
48 Correct 986 ms 145996 KB Output is correct