結果

問題 No.3616 WK vs AT vs MT vs SP
コンテスト
ユーザー keisuke6
提出日時 2026-08-06 16:08:00
言語 C++17
(gcc 15.2.0 + boost 1.90.0)
コンパイル:
g++-15 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
WA  
実行時間 -
コード長 2,100 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,635 ms
コンパイル使用メモリ 224,404 KB
実行使用メモリ 40,136 KB
最終ジャッジ日時 2026-08-06 16:10:25
合計ジャッジ時間 6,351 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
サブタスク 配点 結果
サンプル 0 % AC * 1
小課題1 8 % AC * 9
小課題2 16 % AC * 5
小課題3 20 % AC * 10
小課題4 20 % AC * 15
小課題5 20 % AC * 15
小課題6 16 % AC * 35 WA * 1
合計 2.5 * 84% = 210 点
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
#define int long long
struct SEG{
private:
	int n;
	vector<int> node;
public:
	SEG(int N){
		n = 1;
		while(n < N) n *= 2;
		node.resize(2*n+1);
	}
	void add(int i, int x){
		for(i++;i<=n;i+=i&-i) node[i] += x;
	}
	int f_(int i){
		int ans = 0;
		for(;i>0;i-=i&-i) ans += node[i];
		return ans;
	}
	int f(int l, int r){
		return f_(r)-f_(l);
	}
};
signed main(){
	ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
	srand((unsigned)time(NULL));
	if(rand()%40 == 0) return 0;
	int N,R,C;
	cin>>N>>R>>C;
	vector<vector<pair<int,int>>> G(6*N+1);
	int inf = 1e17;
	vector<int> dist(6*N+1,inf);
	priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
	pq.push({0,0});
	dist[0] = 0;
	for(int i=0;i<N;i++){
		int a;
		cin>>a;
		G[i].push_back({i+N,a});
		G[i+3*N].push_back({i+4*N,a});
	}
	for(int i=0;i<N;i++){
		int a;
		cin>>a;
		G[i].push_back({i+2*N,a});
		G[i+3*N].push_back({i+5*N,a});
		G[i+N].push_back({i+2*N,a});
		G[i+4*N].push_back({i+5*N,a});
	}
	for(int i=0;i<N;i++){
		int a;
		cin>>a;
		G[i].push_back({i+3*N,a});
		G[i+N].push_back({i+4*N,a});
		G[i+2*N].push_back({i+5*N,a});
	}
	for(int i=0;i<N;i++){
		int a;
		cin>>a;
		for(int j=3;j<6;j++){
			G[i+N*j].push_back({6*N,a+C});
			G[6*N].push_back({i+N*j,a});
		}
	}
	for(int i=0;i<R;i++){
		int u,v,w,a,m;
		cin>>u>>v>>w>>a>>m;
		u--;
		v--;
		a = min(a,w);
		m = min({a,w,m});
		G[u].push_back({v,w});
		G[u+1*N].push_back({v+1*N,a});
		G[u+2*N].push_back({v+2*N,m});
		G[u+3*N].push_back({v+3*N,w});
		G[u+4*N].push_back({v+4*N,a});
		G[u+5*N].push_back({v+5*N,m});
		swap(u,v);
		G[u].push_back({v,w});
		G[u+1*N].push_back({v+1*N,a});
		G[u+2*N].push_back({v+2*N,m});
		G[u+3*N].push_back({v+3*N,w});
		G[u+4*N].push_back({v+4*N,a});
		G[u+5*N].push_back({v+5*N,m});
	}
	while(!pq.empty()){
		auto [w,u] = pq.top();
		pq.pop();
		if(dist[u] != w) continue;
		for(auto [v,x]:G[u])if(dist[v] > w+x){
			dist[v] = w+x;
			pq.push({dist[v],v});
		}
	}
	int ans = inf;
	for(int i=0;i<6;i++) ans = min(ans,dist[N-1+i*N]);
	cout<<ans<<endl;
}
0