結果

問題 No.1 道のショートカット
コンテスト
ユーザー iris2617
提出日時 2025-11-18 02:51:29
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 18 ms / 5,000 ms
コード長 1,273 bytes
コンパイル時間 2,386 ms
コンパイル使用メモリ 217,032 KB
実行使用メモリ 11,648 KB
最終ジャッジ日時 2025-11-18 02:51:34
合計ジャッジ時間 4,063 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
#define int long long
#define matsuri pair<int,int>
//const int iris = 1e9+7;
const int iris = 998244353;
using namespace std;

using akari = pair<int,matsuri>;

void solve()
{
	int n,C,V;
	cin>>n>>C>>V;
	vector<vector<vector<tuple<int,int,int> > > > G(n+1, vector<vector<tuple<int,int,int> > >(C+1));
	vector<int> S(V), T(V), Y(V), M(V);
	for(int &x:S)
		cin>>x;
	for(int &x:T)
		cin>>x;
	for(int &x:Y)
		cin>>x;
	for(int &x:M)
		cin>>x;
	vector<vector<int> > dis(n+1, vector<int>(C+1, 1e18));
	for(int i=0;i<V;i++)
	{
		int a=S[i], b=T[i], c=Y[i], d=M[i];
		for(int j=0;j+c<=C;j++)
		{
			G[a][j].emplace_back(b, j+c, d);
			//G[b][j].emplace_back(a, j+c, d);
		}
	}
	dis[1][0]=0;
	priority_queue<akari, vector<akari>, greater<akari> > pq;
	pq.emplace(0, matsuri{1,0});
	while(!pq.empty())
	{
		auto [d,_]=pq.top();
		pq.pop();
		auto [a,x]=_;
		if(dis[a][x]!=d)
			continue;
		for(auto [b,y,c]:G[a][x])
		{
			if(dis[a][x]+c<dis[b][y])
			{
				dis[b][y]=dis[a][x]+c;
				pq.emplace(dis[b][y], matsuri{b,y});
			}
		}
	}
	int ans=1e18;
	for(int i=0;i<=C;i++)
		ans=min(ans, dis[n][i]);
	if(ans==1e18)
		ans=-1;
	cout<<ans<<'\n';
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	int T=1;
	//cin>>T;
	while(T--)
		solve();

	return 0;
}
0