結果

問題 No.1283 Extra Fee
コンテスト
ユーザー ooaiu
提出日時 2026-09-29 22:57:24
言語 C++23
(gcc 15.3.0 + boost 1.92.0 + ACL)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 284 ms / 2,000 ms
+ 474µs
コード長 1,040 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,113 ms
コンパイル使用メモリ 193,420 KB
実行使用メモリ 78,032 KB
最終ジャッジ日時 2026-09-29 22:57:57
合計ジャッジ時間 8,797 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <vector>
#include <queue>
#include <iostream>
#include <cassert>
#include <algorithm>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
int N, M;
vector<pair<int,long>>G[505*505*2];
long A[505][505];
long dp[505*505*2];
int main() {
	cin >> N >> M;
	rep(i, M) {
		int a, b, c;
		cin >> a >> b >> c;
		a--, b--;
		A[a][b] = c;
	}
	const int dx[] = {1, 0, -1, 0, 1};
	rep(i, N) rep(j, N) {
		rep(r, 4) {
			int ni = i + dx[r], nj = j + dx[r + 1];
			if (ni < 0 || nj < 0 || ni >= N || nj >= N) continue;
			long cost = 1 + A[i][j];
			int a = i * N + j, b = ni * N + nj;
			G[b].push_back({a, cost});
			G[b].push_back({a + N*N, 1});
			G[b + N*N].push_back({a + N*N, cost});
		}
	}
	using S = pair<long, int>;
	priority_queue<S, vector<S>, greater<S>> pq;
	pq.push({0, 0});
	rep(i, N * N * 2) dp[i] = 1e18;
	dp[0] = 0;
	while(pq.size()) {
		auto[e, v] = pq.top();pq.pop();
		if(dp[v]!=e) continue;
		for(auto[nv,cst]:G[v])if(dp[nv]>dp[v]+cst)dp[nv]=dp[v]+cst,pq.push({dp[nv],nv});
	}
	cout<<dp[2*N*N-1]<<endl;
}
0