結果

問題 No.2366 登校
ユーザー vjudge1
提出日時 2025-08-15 19:44:55
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 265 ms / 4,000 ms
コード長 1,917 bytes
コンパイル時間 3,124 ms
コンパイル使用メモリ 284,584 KB
実行使用メモリ 30,760 KB
最終ジャッジ日時 2025-08-15 19:45:02
合計ジャッジ時間 6,072 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
typedef pair <int, int> pii;
#define fi first
#define se second
#define pb push_back
const int MOD = 1e9 + 7;
const int MAX = 80 + 5;

bool vis[MAX][MAX][5*MAX];
ll dist[MAX][MAX][5*MAX];
pii a[MAX][MAX];

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	int n, m, k, t; cin >> n >> m >> k >> t;
	ll tot_time = n - 1 + m - 1;
	
	priority_queue <array<int, 4>, vector<array<int, 4>>, greater <array<int, 4>>> pq;
	for(int i = 0 ; i <= n ; i++){
		for(int j = 0 ; j <= m ; j++){
			for(int l = 0 ; l <= 2*tot_time ; l++){
				dist[i][j][l] = (int)1e15;
				vis[i][j][l] = 0;
				a[i][j] = {0, 0};
			}
		}
	}
	
	for(int i = 1 ; i <= k ; i++){
		int x, y, v, w; cin >> x >> y >> v >> w;
		a[x][y] = {v, w};
	}
	dist[1][1][tot_time] = 0;
	pq.push({0, 1, 1, tot_time});
	while(pq.size()){
		auto [dis, x, y, tm] = pq.top();pq.pop();
		
		if(vis[x][y][tm])continue;
		vis[x][y][tm]  =1;
		
		if(tm + 1 <= 2*tot_time){
			if(x + 1 <= n && dis < dist[x + 1][y][tm + 1]){
				dist[x + 1][y][tm + 1] = dis;
				pq.push({dis, x + 1, y, tm + 1});
			}
			if(x - 1 >= 1 && dis < dist[x - 1][y][tm + 1]){
				dist[x - 1][y][tm + 1] = dis;
				pq.push({dis, x - 1, y, tm + 1});
			}
			if(y + 1 <= m && dis < dist[x][y + 1][tm + 1]){
				dist[x][y + 1][tm + 1] = dis;
				pq.push({dis, x, y + 1, tm + 1});
			}
			if(y - 1 >= 1 && dis < dist[x][y - 1][tm + 1]){
				dist[x][y - 1][tm + 1] = dis;
				pq.push({dis, x, y - 1, tm + 1});
			}
		}
		
		if(a[x][y].fi != 0){
			ll f = a[x][y].fi;
			ll s = a[x][y].se;
			
			ll cnt = max(0ll, tm - f + 1);
			if(dis + s < dist[x][y][cnt]){
				dist[x][y][cnt] = dis + s;
				pq.push({dis + s, x, y, cnt});
			}
		}
	}
	
	ll ans = (int)1e15;
	for(int i = 0 ; i <= tot_time + min(t, tot_time) ; i++)ans = min(ans, dist[n][m][i]);
	
	cout << (ans == (ll)1e15 ? -1 : ans) << endl;
	
	return 0;
}
0