제출 #1182812

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1182812		SmuggingSpun	Robot (JOI21_ho_t4)	C++20	0 / 100	22 ms	5448 KiB

Main

#include<bits/stdc++.h>
#define taskname "D"
using namespace std;
typedef long long ll;
const ll INF = 1e18;
template<class T>bool minimize(T& a, T b){
	if(a > b){
		a = b;
		return true;
	}
	return false;
}
const int lim = 1e5 + 5;
const int LIM = 2e5 + 5;
int n, m, a[LIM], b[LIM], c[LIM], p[LIM];
vector<int>g[lim];
namespace sub1{
	struct Data{
		int u, c;
		ll w;
		Data(int _u, int _c, ll _w) : u(_u), c(_c), w(_w) {}
		friend bool operator <(const Data a, const Data b){
			return a.w > b.w;
		}
	};
	void solve(){
		vector<vector<ll>>d(n + 1, vector<ll>(m + 1, INF));
		priority_queue<Data>pq;
		pq.push(Data(1, 0, d[1][0] = 0));
		vector<int>cnt(m + 1, 0);
		while(!pq.empty()){
			Data current = pq.top();
			pq.pop();
			if(current.w == d[current.u][current.c]){
				cnt[current.c] = 1;
				for(int& i : g[current.u]){
					cnt[c[i]]++;
				}
				for(int& i : g[current.u]){
					int v = a[i] ^ b[i] ^ current.u;
					if(cnt[c[i]] == 1 && minimize(d[v][c[i]], current.w)){
						pq.push(Data(v, c[i], d[v][c[i]]));
					}
					if(minimize(d[v][0], current.w + p[i])){
						pq.push(Data(v, 0, d[v][0]));
					}
				}
				cnt[current.c] = 0;
				for(int& i : g[current.u]){
					cnt[c[i]] = 0;
				}
			}
		}
		ll ans = *min_element(d[n].begin(), d[n].end());
		cout << (ans == INF ? -1LL : ans);
	}
}
namespace sub23{
	void solve(){
		
	}
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	if(fopen(taskname".inp", "r")){
		freopen(taskname".inp", "r", stdin);
	}
	cin >> n >> m;
	for(int i = 1; i <= m; i++){
		cin >> a[i] >> b[i] >> c[i] >> p[i];
		g[a[i]].emplace_back(i);
		g[b[i]].emplace_back(i);
	}
	if(n <= 1000 && m <= 2000){
		sub1::solve();
	}
	else{
		sub23::solve();
	}
}

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'int main()':
Main.cpp:66:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |                 freopen(taskname".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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