oj.uz

답안 #478036

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
478036 2021-10-05T07:37:48 Z lequocbinh Robot (JOI21_ho_t4) C++17
0 / 100
 436 ms 42804 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
# define TASK ""
# define FOR(i,x,y) for(int i = x; i <= y; ++i)
# define all(x) x.begin(), x.end()
# define pii pair< ll , ll >
template <class T>
bool inArr(T obj, vector<T> x){
	return find(all(x), obj) != x.end();
}

int getbit(int i, int j){
	return ( 1 << (j-1) ) & i;
}

const long long MAXN = 1e5 + 5;
ll N, M;
struct binh{
	ll v,c,p;
};	
vector< binh > g[MAXN];
map < ll , ll > m[MAXN];

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	if(fopen(TASK".inp", "r")){
		freopen(TASK".inp", "r", stdin);
		freopen(TASK".out", "w", stdout);
	}

	cin >>N >> M;
	for(int i = 1; i <= M; ++i){
		ll u,v,c,p;
		cin >> u >> v >> c >> p;
		g[u].push_back({v,c,p});
		g[v].push_back({u,c,p});
		++m[u][c];
		++m[v][c];
	}


	priority_queue< pii, vector< pii >, greater< pii > > q;
	q.push({0, 1});

	vector< ll > d(N + 1, LLONG_MAX);
	vector< ll > vis(N + 1, 0);
	d[1] = 0;
	while(q.size()){
		auto [cost, u] = q.top(); q.pop();
		if(vis[u]) continue;
		vis[u] = 1;
		for(auto [v, c, p] : g[u]){
			if(m[u][c] == 1){
				d[v] = min(d[v], cost);
				q.push({cost, v});
			}
			else if(d[v] > cost + p){
				q.push({d[v] = cost + p, v});
			}
		}
	}

	if(d[N] != LLONG_MAX) cout << d[N]; else cout << -1;

	return 0;
}

Compilation message

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

Subtask #1
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 7244 KB Output is correct
2 Correct 4 ms 7244 KB Output is correct
3 Correct 4 ms 7244 KB Output is correct
4 Correct 4 ms 7244 KB Output is correct
5 Correct 4 ms 7360 KB Output is correct
6 Correct 4 ms 7244 KB Output is correct
7 Incorrect 4 ms 7380 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 95 ms 19308 KB Output is correct
2 Correct 39 ms 13128 KB Output is correct
3 Correct 101 ms 23736 KB Output is correct
4 Correct 66 ms 15392 KB Output is correct
5 Incorrect 436 ms 42804 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 7244 KB Output is correct
2 Correct 4 ms 7244 KB Output is correct
3 Correct 4 ms 7244 KB Output is correct
4 Correct 4 ms 7244 KB Output is correct
5 Correct 4 ms 7360 KB Output is correct
6 Correct 4 ms 7244 KB Output is correct
7 Incorrect 4 ms 7380 KB Output isn't correct
8 Halted 0 ms 0 KB -